这份代码基于Quick Sort。已经过了，但是需要添加随机数。

在没有随机数的情况下，#3和#4会TLE。在隔壁力扣也是一样。

请大佬们帮忙看看，是毒瘤数据还是我写出问题了？

#include <iostream>
#include <vector>
#include <random>
using std::vector;

std::mt19937 rand_gen(std::random_device{}());

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        quick_sort(nums, 0, nums.size());
        return nums;
    }

    void quick_sort(vector<int>& nums, uint const begin, uint const end) {
        if(begin + 1 >= end)
            return;
        std::uniform_int_distribution<uint> rd(begin, end-1);
        std::swap(nums[begin], nums[rd(rand_gen)]); //随机选择middle value, 删除会TLE
        uint left = begin, mid = begin + 1,right = begin + 1; 
        // 在[begin,left)维护小于val的序列，在[left,mid)维护等于val的序列，在[mid,right)维护大于val的序列，right右侧为待处理序列
        for(int val = nums[begin]; right < end; right++)
            if(nums[right] == val) {
                std::swap(nums[mid], nums[right]);
                mid++;
            }
            else if(nums[right] < val) {
                std::swap(nums[mid], nums[right]);
                std::swap(nums[left], nums[mid]);
                left++;
                mid++;
            }
            // 每次右移right处理一个数，如果大于val就什么都不用做，等于val则移到mid最后一个，小于val则移到left最后一个。
        quick_sort(nums, begin, left);
        quick_sort(nums, mid, end);
    }

};
int main() {
    int n;
    scanf("%d", &n);
    std::vector<int> nums(n);
    for(int i = 0; i < n; ++i)
        scanf("%d", &nums[i]);
    Solution solve;
    solve.sortArray(nums);
    for(auto const e:nums)
        printf("%d ",e);
    return 0;
}