目录
一、什么是快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。
它的基本思想为：
- 任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值。
- 然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
二、代码实现
2.1 hoare版本
2.1.1 思路
采取先部分后整体的思路进行讲解
- 考虑单次
- 右指针先去找比基准值小的的位置
- 左指针去找比基准值大的位置
- 两个位置进行交换
- 重复上述过程，直到左指针等于右指针。此时实现了相遇位置左边的值都小于基准值，右边的值都大于基准值。
- 按照基本思想，将此相遇位置与基准值进行交换。就完成了单趟排序
- 考虑整体
- 采用类似二分法的思路，不断分成小的区间
- 停止二分的条件是：左右区间重合（即左区间的值等于右区间）或者 区间不存在（即左区间的值大于右区间）
- 每次递归传值：右区间为[起始位置，相遇位置的前一个位置]；左区间为[相遇位置的后一个位置，结束位置]
2.1.2 C语言源码
void Hoare(int* a, int left, int right)
{
//递归结束条件
if (left >= right)
{
return;
}
int begin = left;
int end = right;
//单趟
while (begin < end)
{
//先右取小
while (begin < end && a[end] > a[left])
{
end--;
}
//后左取大
while (begin < end && a[begin] <= a[left])
{
begin++;
}
//交换
Swap(&a[begin], &a[end]);
}
Swap(&a[begin], &a[left]);
//递归
//左区间
Hoare(a, left, begin - 1);
//右区间
Hoare(a, begin + 1, right);
}2.2 挖坑法
2.2.1 思路
挖坑法提出的目的是解决Hoare版本不易于理解的问题，算法效率上没有任何提升。
- 考虑单次：
- 将基准值存起来。
- 右指针找小，放入原先坑位，形成新的坑位。
- 左指针找大，放入原先坑位，形成新的坑位。
- 最后将相遇位置的坑位放入基准值
- 考虑整体：
- 与Hoare版本递归思路如出一辙，不再进行详细讲解
2.2.2 C语言源码
void DigHole(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int key = a[left];
int begin = left;
int end = right;
while (begin < end)
{
//先从右找出比key小的值
while (begin < end && a[end] > key)
{
end--;
}
//放到坑位上
a[begin] = a[end];
//再从左找出比key大的值
while (begin < end && a[begin] <= key)
{
begin++;
}
//放到坑位上
a[end] = a[begin];
}
a[begin] = key;
//左区间
DigHole(a, left, begin - 1);
//右区间
DigHole(a, begin + 1, right);
}2.3 前后指针版本
2.3.1 思路
前后指针版本大大节约了代码量，是推荐的快速排序实现的版本
- 考虑单次：
- prev指针指向起始位置，cur指针指向prev的下一个位置
- 如果cur指向的值小于基准值，1.prev先向前移动 2.然后与cur指针指向的位置交换 3.最后cur指针移动到下一个位置（实际上没有进行交换，仅仅是cur指针与prev指针一起移动到下一个位置）
- 如果cur指针指向的值大于基准值，cur指针一直移动直到找到比基准值小的位置为止。将此位置与prev指针指向的下一个位置交换。
- 最后将prev指向的位置与基准值位置交换
- 结束条件是cur指针越界
- 考虑整体：
- 与Hoare版本递归思路如出一辙，不再进行详细讲解
2.3.2 C语言源码
void DoublePoint(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int prev = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)
{
if (a[cur]<a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
//左区间
DoublePoint(a, left, keyi - 1);
//右区间
DoublePoint(a, keyi + 1, right);
}
三、效率优化
3.0 时间复杂度分析
一般情况下的时间复杂度类似于二叉树的时间复杂度计算为 O(nlogn)
最坏的情况下，即为给定数组本身是有序的，仍然需要分区间来交换。此时的情况类比于极端的单叉树，时间复杂度为O(n^2)
所以基准值的选择是提高快速排序效率的关键，下述的三数取中法就是解决方法之一
3.1 三数取中法
每次取出区间端点以及区间中点的值比较，取中间值，这样就可以规避上述问题
int GetMidi(int* a, int left, int right)
{
int midi = (left + right) / 2;
int maxi = 0;
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
return midi;
}
else if(a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
else
{
if (a[midi] > a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}3.2 小区间优化
综合选取一个时间复杂度、空间复杂度较小且稳定性高的排序——插入排序
具体讲解请点击：常见排序算法之插入排序-CSDN博客
四、非递归写法
递归需要创建栈帧，极端情况下可能会导致栈溢出。所以采用模拟递归版本实现快速排序是非常必要的
4.1 思路
快速排序采用递归的本质目的是存储了每次排序的区间，递归到最小区间然后逐层解决问题。很明显栈的先进后出的特性满足我们的需求。
栈的源码及详解请点击：数据结构之栈-CSDN博客
- 考虑单次
- 左右区间入栈
- 左右区间出栈
- 采用上述三个版本中的一个进行单趟排序（下述代码采用了双指针版本）
- 考虑循环
- 满足成为一个区间的条件（即左端点小于右端点），继续将左右区间入栈
- 先处理左区间，再处理右区间
- 循环结束条件为：栈内没有元素——即所有区间都处理完毕
4.2 C语言源码
void QuickSort(int* a, int left, int right)
{
ST st;
STInit(&st);
STPush(&st, right);
STPush(&st, left);
while (STEmpty(&st)==false)
{
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
//单趟
int prev = begin;
int cur = begin + 1;
int keyi = begin;
while (cur <= end)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
//模拟递归
//左区间
if (keyi + 1 < end)
{
STPush(&st, end);
STPush(&st, keyi+1);
}
//右区间
if (begin < keyi - 1)
{
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
STDestroy(&st);
}
