快速排序的一切

一、原理

详见各种算法原理

二、实现

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


void quickSort(vector<int> &nums, int left, int right)
{
    if (left >= right)
        return;

    int leftIndex = left;
    int rightIndex = right;
    int curValue = nums[left];
    // 找到curValue的在数组中的最终位置
    while (leftIndex < rightIndex)
    {
        // 从右向左找到第一个小于curValue的
        while (leftIndex < rightIndex && nums[rightIndex] >= curValue)
        {
            rightIndex--;
        }
        if (leftIndex < rightIndex)
            nums[leftIndex++] = nums[rightIndex];
        // 从左向右找到第一个大于等于curValue的
        while (leftIndex < rightIndex && nums[leftIndex] < curValue)
        {
            leftIndex++;
        }
        if (leftIndex < rightIndex)
            nums[rightIndex--] = nums[leftIndex];
    }

    //assert(leftIndex == rightIndex);
    // 此时 leftIndex == rightIndex，也就是curValue的最终位置
    nums[leftIndex] = curValue;

    quickSort(nums, left, leftIndex - 1);
    quickSort(nums, leftIndex + 1, right);

}


int main()
{
    vector<int> nums = {1, 3, 10, 4, 8, 6, 3, 9, 2, 5, 7};
    quickSort(nums, 0, nums.size() - 1);
    for (int i = 0; i < nums.size(); ++i)
        cout << nums[i] << " ";
    return 0;
}

三、时间复杂度

简单明了 😛