快速排序算法原理及多种实现方式

1. 快排主框架

快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法。 其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

简单地说，就是将数组分成左右两个部分，左部分都大于（或小于）中间的基准值，右部分都小于（或大于）中间的基准值，然后不断重复上述过程，直到数组完全有序。

// 快排主框架
void QuickSort(int* a, int left, int right) {
    if (left >= right) return;
    int mid = PartSort(a, left, right);
    QuickSort(a, left, mid - 1);
    QuickSort(a, mid + 1, right);
}

那么显然快排最关键的就是 PartSort 这个函数怎么实现了，这个函数要实现：找到基准值并将数据按照大小划分到基准值的两侧。

1. 时间复杂度：O(nlogn)
2. 空间复杂度：O(logn)

2. 快排的不同实现

这里的 PartSort 函数的实现有很多种，这里介绍 3 种。

2.1 Hoare 版本

算法思路

1. 创建左右指针，确定基准值
2. 从右向左找出比基准值小的数据，从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环
3. 跳出循环后，交换 right 和 key

问题 1：为什么跳出循环后 right 位置的值一定不大于 key? 当 left > right 时，即 right 走到 left 的左侧，而 left 扫描过的数据均不大于 key，因此 right 此时指向的数据一定不大于 key

问题 2：当 left==right 时要不要跳出循环？ 不能，因为此时不知道 left 和 right 同时指向的这个值的大小，必须让 right 或者 left 额外多走一步。

我们通过这三个场景来分析问题 1 并详细解释 Hoare 版本的思路： 首先我们选定第一个元素为基准值（实际上选择基准值还有其他更好地方式，但这里先简化），然后将 left=1，right=numsSize-1，也就是除了第一个元素外，数组的头和尾。

注：以升序为例。 场景一： left<key，left++；right > key，right 不动。 left++,left++,left 指向 7。 left 和 right 交换数据，数组变为：

int a[]={6,1,2,,,};