2022-04-29 快排

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        QuickSort(nums, 0, nums.size() - 1);
        return nums;
    }
    void QuickSort(vector<int>& nums, int begin, int end) {
        if (begin > end) {  // begin = end时返回本身
            return;
        }
        int temp = nums[begin];
        int i = begin;
        int j = end;
        while (i != j ) {
            while (nums[j] >= temp && j > i) {   //卡住的数字肯定小于temp
                j--;
            }
            while (nums[i] <= temp && i < j) {
                i++;
            }
            if (j > i) {                  // 如果两边都找到就换，找不到就等着
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }

        nums[begin] = nums[i];    //直接交换卡住的数字
        nums[i] = temp;
        QuickSort(nums, begin, i - 1);
        QuickSort(nums, i + 1, end);
    }
};

    void random_QuickSort(vector<int>& nums, int begin, int end) {
        if (begin >= end) {
            return;
        }
        // 选取随机数放到第一位
        int rand_index = rand() % (end - begin);
        int temp = nums[begin + rand_index];
        nums[begin + rand_index] = nums[begin];
        nums[begin] = temp;
        
        // 正常快排逻辑
        int i = begin;
        int j = end;
        
        while (i != j) {
            while (nums[j] >= temp && j > i) {
                j--;
            }
            while (nums[i] <= temp && i < j) {
                i++;
            }
            if (j > i) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        nums[begin] = nums[i];
        nums[i] = temp;
        random_QuickSort(nums, begin, i - 1);
        random_QuickSort(nums, i + 1, end);
    }