1. 快排

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        quick_sort(nums, 0, nums.size() - 1);
        return nums;
    }
    void quick_sort(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int left = l, right = r;
        swap(nums[l], nums[(l + r) / 2]);
        int pivot = nums[l];
        while (l < r) { //循环体内只扔了一对次，得一直扔到l==r
            // 这里的l<r，是怕r为了找这次要扔的数，跑到l左侧那就没必要了，因为r右侧都是比Pivot大的，l左侧都是比pivot小的，这里l和r都是一个位子一个位子移动的，只要移动到l和r重合，就已经完成使命了。如果r还要继续左移，
            //下面这两个while必须有一个有等于的，否则就会死循环，因为l<r并且谁的值都不变，没有脱离这个循环的改变
            while (nums[r] >= pivot && l < r) r--;//必须得r先扔给l，因为pivot=nums[l]，l现在的位置是坑
            nums[l] = nums[r];
            while (nums[l] <= pivot && l < r) l++;
            nums[r] = nums[l];
        }
        //出循环肯定是因为l==r所以，这个l/r的坑就是给pivot留的
        nums[l] = pivot;
        quick_sort(nums, left, l - 1);
        quick_sort(nums, l + 1, right);
    }
};

2. 堆排