我用的是lomuto paritition的方式，在后两个测试用例上超时。代码如下：

#include<vector>
#include<iostream>
using namespace std;

int partition(vector<int>& nums, int left, int right){
    int pivot = rand() % (right - left + 1) + left;
    swap(nums[pivot], nums[left]);
    int v = nums[left];
    int i = left + 1;
    for(int j = left + 1; j <= right; ++j){
        if(nums[j] < v){
            if(i == j){
                ++i;
            } else{
                swap(nums[i++], nums[j]);
            }
        }
    }
    swap(nums[left], nums[i - 1]);
    return i - 1;
}

void quickSort(vector<int>& nums, int left, int right){
    if(left >= right) return;
    int mid = partition(nums, left, right);
    quickSort(nums, left, mid - 1);
    quickSort(nums, mid + 1, right);
}

int main(){
    int N;
    cin >> N;
    vector<int> nums(N, 0);
    for(int i = 0; i < N; ++i){
        cin >> nums[i];
    }
    quickSort(nums, 0, N - 1);
    for(int i = 0; i < N; ++i){
        if(i < N - 1) cout << nums[i] << " ";
        else cout << nums[i] << endl;
    }
}

然而，换成Hoare partition或三路快排就能过。为什么呢？