快排由于优秀的时间复杂度及较低的常数项，为大家所喜爱，不管是工程上的排序还是日常的算法题目排序都经常使用。

下面我将列出快排的核心函数partition()：

• 一种简短的写法：

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

• 经典快排partition：

int partition(vector<int>& nums, int left, int right){
    int pivot = rand() % (right - left + 1) + left; // 使用随机函数来取轴心
    swap(nums[pivot], nums[right]);
    int R = right;                                    // 以最后一个元素为轴心
    while(left < right){
        while(left < right && nums[left] <= nums[R])  // 从左往右扫描，找第一个大于轴心
            ++left;
        while(left < right && nums[right] > nums[R])  // 从右往左扫描，找第一个小于等于轴心
            --right;
        if(left < right)
            swap(nums[left], nums[right]);
    }
    swap(nums[R], nums[left]);                        // 与轴心交换
    return pivot;                                     // 返回轴心，即分割点，返回left也行
}

• 基于经典快排partition的优化：

int partition(vector<int>& nums, int left, int right){
    int pivot = rand() % (right - left + 1) + left; // 使用随机函数来取轴心
    swap(nums[pivot], nums[right]);
    int temp = nums[right];                                    
    while(left < right){
        while(left < right && nums[left] <= temp)
            ++left;
        nums[right] = nums[left];
        while(left < right && nums[right] > temp)
            --right;
        nums[left] = nums[right];
    }
    nums[left] = temp;
    return left;
}

以上三种partition函数的时间复杂度和空间复杂度都一致：

• 时间复杂度：O（N）
• 空间复杂度：O（1）

但是由于实现细节不同，第三种与第二种比较而言移动元素的次数更少（swap函数需要3次移动），所以实际上更快、更优，而第一种相对后两种性能更差一些。通过测试，也印证我刚刚的说法。

测试源码：

#include <vector>
#include <ctime>
#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[right]);
    for (int i = left; i < right; i++) {
        if (nums[i] < nums[right])
            swap(nums[left++], nums[i]);
    }
    swap(nums[left], nums[right]);
    return left;
}

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);
}

void quickSort(vector<int> &nums) {
    if (nums.size() < 2)
        return;
    quickSort(nums, 0, nums.size() - 1);
}

//*********************第二种*****************************
int partition2(vector<int>& nums, int left, int right) {
    int pivot = rand() % (right - left + 1) + left; // 使用随机函数来取轴心
    swap(nums[pivot], nums[right]);
    int R = right;                                    // 以最后一个元素为轴心
    while (left < right) {
        while (left < right && nums[left] <= nums[R])  // 从左往右扫描，找第一个大于轴心
            ++left;
        while (left < right && nums[right] > nums[R])  // 从右往左扫描，找第一个小于等于轴心
            --right;
        if (left < right)
            swap(nums[left], nums[right]);
    }
    swap(nums[R], nums[left]);                        // 与轴心交换
    return pivot;                                     // 返回轴心，即分割点，返回left也行
}

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

void quickSort2(vector<int> &nums) {
    if (nums.size() < 2)
        return;
    quickSort2(nums, 0, nums.size() - 1);
}
//*********************第三种*****************************
int partition3(vector<int> &nums, int left, int right) {
    int pivot = rand() % (right - left + 1) + left; // 使用随机函数来取轴心
    swap(nums[pivot], nums[right]);
    int temp = nums[right];
    while (left < right) {
        while (left < right && nums[left] <= temp)
            ++left;
        nums[right] = nums[left];
        while (left < right && nums[right] > temp)
            --right;
        nums[left] = nums[right];
    }
    nums[left] = temp;
    return left;

}

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

void quickSort3(vector<int> &nums) {
    if (nums.size() < 2)
        return;
    quickSort3(nums, 0, nums.size() - 1);
}

// 生成长度为n，值为0~INT_MAX-1的数组
vector<int> GenerateVec(int n) {
    vector<int> res(n);
    for (int i = 0; i < n; ++i)
        res[i] = rand() % INT_MAX;
    return res;
}

int main() {
    srand((int)time(0));
    // 测试用例
    vector<vector<int>> input(100000, vector<int>(100));
    for (int i = 0; i < 100000; ++i)
        input[i] = GenerateVec(100);


    clock_t begin, end;
    begin = clock();
    for (int i = 0; i < 10000; ++i)
        quickSort(input[i]);
    end = clock();
    cout << "第一种算法耗时：" << end - begin << "ms" << endl;

    begin = clock();
    for (int i = 0; i < 10000; ++i)
        quickSort2(input[i]);
    end = clock();
    cout << "第二种算法耗时：" << end - begin << "ms" << endl;

    begin = clock();
    for (int i = 0; i < 10000; ++i)
        quickSort3(input[i]);
    end = clock();
    cout << "第三种算法耗时：" << end - begin << "ms" << endl;

    return 0;
}

这里我选择随机生成10万组长度为100的数组进行测试，得出来的结果也显而易见：当数据量越大时，差距也越大。

测试结果

PS

对于轴心的选择除了用随机函数，还可以使用三点中值：实际上我测试了一下不如rand快=_=

int medianOfThree(vector<int>& nums, int l, int r) {
    int m = l + (r - l) / 2;
    if (nums[l] < nums[m]) {
        if (nums[m] < nums[r])
            return m;
        else if (nums[r] < nums[l])
            return l;
        else
            return r;
    }
    else if (nums[l] < nums[r]) {
        return l;
    }
    else if (nums[m] < nums[r]) {
        return r;
    }
    else
        return m;
}