class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        sort(nums, 0, nums.size() - 1);
        return nums;
    }
    
    void sort(vector<int>& nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = partition(nums, left, right);
        sort(nums, left, mid - 1);
        sort(nums, mid + 1, right);
    }
    
    int partition(vector<int> &nums, int left, int right) {
        if (left == right) {
            return left;
        }
        
        int base = nums[right];
        int l = left, r = right - 1;
        int i = left;
        while (i < right) {
            if (nums[i] <= base) {
                swap(nums[i], nums[l]);
                ++l;
            }
            ++i;
        }
        swap(nums[right], nums[l]);
        return l;
    }
};

快速选择

平均O(N)时间, 找到数组中第K大的数

int quickSelect(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    int target = nums.size() - k; // 第 k 大就是第 n-k 小

    while (left <= right) {
        int pivot = nums[right];
        int i = left;
        for (int j = left; j < right; ++j) {
            if (nums[j] <= pivot) {
                swap(nums[i++], nums[j]);
            }
        }
        swap(nums[i], nums[right]);

        if (i == target) return nums[i];
        else if (i < target) left = i + 1;
        else right = i - 1;
    }
    return -1; // 不可能到这里
}