冒泡排序

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for(int i = nums.size()-1;i > 0;i--)
        {
            for(int j = 0;j < i;j++)
                if(nums[j] > nums[j+1])
                    swap(nums[j],nums[j+1]);
        }
        return nums;
    }
};

执行结果：

Time Limit Exceeded
Details 
Last executed input
[5864,-12333,4151,-6239,-10306,10866,-7013,13195,-8855,1150,-560,3227,10387,-2329,5169,-19527,2689,597,4255,-13697,12495,19719,15995,8991,-12859,5601,8195,3943,16216,-19677,15590,10316,-4255,45,-6508,-5416,4993,15278,-6015,-18843,-8400,-6994,3608,-7695,-14698,-2684,8753,18019,3266,-10860,-14354,8708,19037,-16188,4932,1403,-10571,18368,-9786,13410,1686,-17352,-13827,6647,16747,2664,-15830,13673,-10248,2115,-19074,-919,4382,18718,-7449,-16031,333,-14066,-2505,-9975,-226,-18986,17487,-3498,-17203,-3506,8462,-191,10563,10160,12627,-8306,9439,-16640,4586,-12067,-19904,-5607,-15989,15651,-18358,-850,-850,3472,8969,13113,1269,4808,123,16848,9857,17099,14566,4854,-19826,957,-10325,-8686,11542,-10343,-16353,-9446,-18914,3242,5897,-19881,-16532,14827,-5840,2873,-10823,-4545,5028,-4985,15482,-8196,14376,-11370,4044,-18929,15051,5562,15969,-4135,13438,12928,-5472,10521,11392,-16511,461,12535,12429,13353,5861,6523,2158,16888,8264,580,-18042,-10113,-809,3072,14636,-12239,-18102,8235,14993,-15364,-19
View All

选择排序

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        //选择排序
        for(int i = 0;i < nums.size() - 1;i++)
        {
            int loc = i;
            for(int j = i;j < nums.size();j++)
                if(nums[j] < nums[loc])
                    loc = j;
            swap(nums[i],nums[loc]);
        }
        return nums;
    }
};

运行结果Time Limit Exceeded，我们发现O(n2)复杂度的算法是行不通的。

快速排序

class Solution {
    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i + 1], nums[r]);
        return i + 1;
    }
    int randomized_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }
    void randomized_quicksort(vector<int>& nums, int l, int r) {
        if (l < r) {
            int pos = randomized_partition(nums, l, r);
            randomized_quicksort(nums, l, pos - 1);
            randomized_quicksort(nums, pos + 1, r);
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));
        randomized_quicksort(nums, 0, (int)nums.size() - 1);
        return nums;
    }
};

运行效率:

执行用时：80 ms, 在所有 C++ 提交中击败了29.01%的用户
内存消耗：27.8 MB, 在所有 C++ 提交中击败了28.64%的用户

归并排序

youtube上有个up主讲解的非常清晰，归并排序

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        merge_sort(nums,0,nums.size() - 1);
        return nums;
    }
private:
    void merge_sort(vector<int>& nums,int l,int r)
    {
        if(l >= r) return;
        int m = l + (r - l)/2;
        merge_sort(nums,l,m);
        merge_sort(nums,m + 1,r);
        merge(nums,l,m,r);
    }
    
    void merge(vector<int>& nums,int l,int m,int r)
    {
        vector<int> tmp(r-l+1);
        int p = l,q = m + 1,loc = 0;
        while(p <= m && q <= r)
        {
            if(nums[p] <= nums[q])
                tmp[loc++] = nums[p++];
            else
                tmp[loc++] = nums[q++];
        }
        while(p <= m) tmp[loc++] = nums[p++];
        while(q <= r) tmp[loc++] = nums[q++];
        for(int i = 0;i < loc;i++)
            nums[l + i] = tmp[i];
    }
};

归并排序运行效率：

执行用时：240 ms, 在所有 C++ 提交中击败了5.02%的用户
内存消耗：70.4 MB, 在所有 C++ 提交中击败了5.03%的用户

在力扣提交代码后看到提交榜击败100%的一个大佬提交的代码：

class Solution {
public:
    // 插入
    void Insertion_Sort(vector<int>& nums)
    {
        for (int i = 1; i < nums.size(); i++)
        {
            int t = nums[i];
            int j = i - 1;
            for (; j >= 0 && nums[j] > t; j--)
            {
                nums[j + 1] = nums[j];
            }
            nums[j + 1] = t;
        }
    }
    
    // 冒泡
    void Bubble_Sort(vector<int>& nums)
    {
        for (int i = 0; i < nums.size(); i++)
        {
            bool flag = false;
            for (int j = nums.size() - 1; j > i; j--)
            {
                if (nums[j - 1] > nums[j])
                {
                    swap(nums[j - 1], nums[j]);
                    flag = true;
                }
            }
            if (!flag)
            {
                return;
            }
        }
    }
    
    // 选择
    void Selection_Sort(vector<int>& nums)
    {
        for (int i = 0; i < nums.size(); i++)
        {
            int minIndex = i;
            for (int j = i + 1; j < nums.size(); j++)
            {
                if (nums[minIndex] > nums[j])
                {
                    minIndex = j;
                }
            }
            swap(nums[i], nums[minIndex]);
        }
    }
    
    // 希尔
    void Shell_Sort(vector<int>& nums)
    {
        for (int gap = nums.size() / 2; gap > 0; gap /= 2)
        {
            for (int i = gap; i < nums.size(); i++)
            {
                int t = nums[i];
                int j = i - gap;
                for (; j >= 0 && nums[j] > t; j -= gap)
                {
                    nums[j + gap] = nums[j];
                }
                nums[j + gap] = t;
            }
        }
    }
    // 堆
    void Adjust(vector<int>& nums, int n, int i)
    {
        int maxn = i, l = i * 2 + 1, r = i * 2 + 2;
        if (l < n && nums[maxn] < nums[l])
        {
            maxn = l;
        }
        if (r < n && nums[maxn] < nums[r])
        {
            maxn = r;
        }
        if (maxn != i)
        {
            swap(nums[i], nums[maxn]);
            Adjust(nums, n, maxn);
        }
    }

    void Heap_Sort(vector<int>& nums)
    {
        int n = nums.size();
        for (int i = n / 2 - 1; i >= 0; i--)
        {
            Adjust(nums, n, i);
        }
        for (int i = n - 1; i >= 0; i--)
        {
            swap(nums[0], nums[i]);
            Adjust(nums, i, 0);
        }
    }

    // 归并
    void Merge_Sort(vector<int>& nums, vector<int>& T, int l, int r)
    {
        if (r - l < 2)
        {
            return;
        }
        int m = l + (r - l) / 2;
        Merge_Sort(nums, T, l, m);
        Merge_Sort(nums, T, m, r);
        int p = l, q = m, i = l;
        while (p < m || q < r)
        {
            if (q >= r || p < m && nums[p] <= nums[q])
            {
                T[i++] = nums[p++];
            }
            else
            {
                T[i++] = nums[q++];
            }
        }
        for (i = l; i < r; i++)
        {
            nums[i] = T[i];
        }
    }

    // 快速
    void Quick_Sort(vector<int>& nums, int l, int r)
    {
        if (l + 1 >= r)
        {
            return;
        }
        int i = l, j = r - 1, pivot = nums[l];
        while (i < j)
        {
            while (i < j && pivot <= nums[j])
            {
                j--;
            }
            nums[i] = nums[j];
            while (i < j && pivot >= nums[i])
            {
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = pivot;
        Quick_Sort(nums, l, i);
        Quick_Sort(nums, i + 1, r);
    }

    // 计数
    void Count_Sort(vector<int>& nums)
    {
        int minn = *min_element(nums.begin(), nums.end());
        int maxn = *max_element(nums.begin(), nums.end());
        vector<int> cnt(maxn - minn + 1, 0);
        for (int& num : nums)
        {
            cnt[num - minn]++;
        }
        int cur = 0;
        for (int i = 0; i < cnt.size(); i++)
        {
            while(cnt[i] > 0)
            {
                nums[cur++] = i + minn;
                cnt[i]--;
            }
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        // Insertion_Sort(nums);
        // Bubble_Sort(nums);
        // Selection_Sort(nums);
        // Shell_Sort(nums);
        // vector<int> T(nums);
        // Merge_Sort(nums, T, 0, nums.size());
        // Quick_Sort(nums, 0, nums.size());
        // Heap_Sort(nums);
        Count_Sort(nums);
        return nums;
    }
};

这里我们重点介绍下计数排序：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        Count_Sort(nums);
        return nums;
    }
private:
    void Count_Sort(vector<int>& nums) {
        int min = *min_element(nums.begin(),nums.end());
        int max = *max_element(nums.begin(),nums.end());
        int loc = 0;
        vector<int> count(max-min+1,0);
        for(auto num:nums) {
            count[num - min]++;
        }

        for(int i = 0;i < count.size();i++) {
            while(count[i] > 0)
            {
                nums[loc++] = i + min;
                count[i]--;
            }
        }
        
    }
};

运行效率:

执行用时：56 ms, 在所有 C++ 提交中击败了49.69%的用户
内存消耗：28.5 MB, 在所有 C++ 提交中击败了11.42%的用户

堆排序实现:

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        Heap_Sort(nums);
        return nums;
    }
private:
    // 堆
    void Adjust(vector<int>& nums, int n, int i)
    {
        int maxn = i,l = 2 * i + 1,r = l + 1;
        if(l < n && nums[l] > nums[maxn])
            maxn = l;

        if(r < n && nums[r] > nums[maxn])
            maxn = r;
        
        if(maxn != i)
        {
            swap(nums[maxn],nums[i]);
            Adjust(nums,n,maxn);
        }
    }

    void Heap_Sort(vector<int>& nums)
    {
        int n = nums.size();
        //从最后一个结点的父结点开始调整
        for (int i = (n-2)/2; i >= 0; i--)
        {
            Adjust(nums, n, i);
        }
        for (int i = n - 1; i >= 0; i--)
        {
            //nums[0](最大值与最后一个元素交换)
            swap(nums[0], nums[i]);
            //重新调整，元素个数变为i
            Adjust(nums, i, 0);
        }
    }
};

heapsort
运行效率:

执行用时：96 ms, 在所有 C++ 提交中击败了18.26%的用户
内存消耗：27.7 MB, 在所有 C++ 提交中击败了45.79%的用户