概述

快速排序的主要思想是分治法，将一个大问题分割成小问题，解决小问题后再合并它们的结果。

实现

1. 从待排序的数组中选择一个元素，作为基准元素（pivot）；
2. 将数组中小于基准元素的元素移到基准元素的左边，将大于基准元素的元素移到基准元素的右边，这个过程称为分区（partition）；
3. 递归地对基准元素左边的子数组和右边的子数组进行排序；
4. 当所有子数组都有序时，整个数组就自然有序了；

代码

快排主框架

void QuickSort(vector<int> &nums, int left, int right)
{
    // 假设按照升序对array数组中[left, right)区间中的元素进行排序
    if (right <= left)
    {
        return;
    }
    // 按照基准值对array数组的 [left, right)区间中的元素进行划分
    int div = PartSort(nums, left, right);
    // 划分成功后以div为边界形成了左右两部分 [left, div-1) 和 [div+1, right)
    // 递归排序[left, div-1)
    QuickSort(nums, left, div - 1);
    // 递归排序[div+1, right)
    QuickSort(nums, div + 1, right);
}

PartSort

Hoare版本快排

int PartSort(vector<int> &nums, int left, int right)
{
    int key = left;
    while (left < right)
    {
        // 右边找大
        while (left < right && nums[right] >= nums[key])
        {
            right--;
        }
        // 左边找小
        while (left < right && nums[left] <= nums[key])
        {
            left++;
        }
        swap(nums[left], nums[right]);
    }
    swap(nums[left], nums[key]);
    return left;
}