912. 排序数组

题目链接

本题使用的是快排解决。

思路：「荷兰国旗」问题，具体思路跳转75. 颜色分类

代码

class Solution {
public:

    void swap(vector<int>& nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    // [L, R]上排序
    void quickSort(vector<int>& nums, int L, int R) {
        if (L >= R) {
            return;
        }
        int left_border = L - 1;       // [L, left_border]小于区域
        int right_border = R + 1;      // [right_border, R]大于区域
        int i = L;
        // 这里很重要，不然会因为数据情况退化成O(n^2)
        int random_index = L + rand() % (R - L + 1);   // 随机取值划分
        int num = nums[random_index];   
        while(i < right_border) {
            if (nums[i] == num) {
                i++;
            } else if(nums[i] < num) {   // 「发货」到小于区域
                swap(nums, i, left_border + 1);
                i++;
                left_border++;
            } else {     // 「发货」到大于区域
                swap(nums, i, right_border - 1);
                right_border--;
                // 注意这里i不能动
            }
        }

        // [L, left_border]小于区域
        // [left_border + 1, right_border - 1] 等于区域 已经有序了
        // [right_border, R]大于区域
        quickSort(nums, L, left_border);    // 小于区域继续快排
        quickSort(nums, right_border, R);    // 大于区域继续快排

    }

    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
        vector<int> ans = nums;
        return ans;
    }
};