快速排序

int partition(std::vector<int>& arr, int l, int r) {
    int pivot = arr[l];
    while (l < r) {
        while (l < r && arr[r] >= pivot) r--;
        arr[l] = arr[r];
        while (l < r && arr[l] <= pivot) l++;
        arr[r] = arr[l];
    }
    arr[l] = pivot;
    return l;
}

void quickSort(std::vector<int>& arr, int l, int r) {
    if (l < r) {
        // random select pivot, can reduce the probability of the worst case complexity
        int i = rand() % (r - l + 1) + l;
        std::swap(arr[l], arr[i]);
        int pos = partition(arr, l, r);
        quickSort(arr, l, pos - 1);
        quickSort(arr, pos + 1, r);
    }
}

void quickSort(std::vector<int>& arr) {
    srand((unsigned)time(NULL));
    quickSort(arr, 0, (int) arr.size() - 1);
}