快速排序

经典的快速排序，先上代码

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if (nums.empty()) {
            return nums;
        }
        srand(time(nullptr));
        sort_array_sub(nums, 0, nums.size()-1);
        return nums;
    }

private:
    void sort_array_sub(std::vector<int>& nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int pos = rand() % (right-left+1) + left;
        std::swap(nums[pos], nums[left]);
        int pivot = nums[left];
        int less = left;
        int more = right+1;
        int j = left+1;
        while (j < more) {
            if (nums[j] < pivot) {
                less++;
                std::swap(nums[less], nums[j]);
                j++;
            } else if (nums[j] == pivot) {
                j++;
            } else {
                more--;
                std::swap(nums[j], nums[more]);
            }
        }
        std::swap(nums[less], nums[left]);
        sort_array_sub(nums, left, less-1);
        sort_array_sub(nums, more, right);
    }
};

我们随机去拿到一个 pivot 点，然后将其放在当前区间的最左边。最左边记为 left，然后我们从 left+1 位置开始遍历，到 right 位置结束。

我们的这个区间可以分为三份，左边部分全部是小于 pivot 的，中间部分全是等于 pivot 的，右边部分全是大于 pivot 的。三个区间分为：[left, less-1], [less, more-1], [more, right]

开始时，less 为 left，more 为 right+1。遍历的过程中，如果遇到的值小于 pivot，则让 less++，然后交换当前这个元素和 less 对应的元素，最后继续向前。始终要想清楚，less 的左边是小于 pivot 的，所以遇到小于 pivot 的值，要让 less 自增

如果当前元素和 pivot 的值相等，那就继续向右遍历即可

如果当前元素大于 pivot 的值，让 more 的值减一，然后调用当前元素和 more 对应的元素。始终要想清楚，more 右边的一定是大于 pivot 的。所以进行调用。特别注意，不要继续向后遍历，而是应该再此遍历当前元素，因为不知道换过来的元素大小

最后遍历完之后，调用 less 和 left 的位置。因为 left 位置就是 pivot 的值。调换完之后从 less 之前就是等于 pivot 的值了。