目录
1.快速排序的思想
快速排序是一种类似于二叉树结构的排序方法。其基本思想为从待排序序列中任取一个元素作为基准值，按照该基准值将待排序序列分割成两个子序列，左子序列中所有元素的值均小于基准值，右子序列中所有元素的值均大于基准值，左右子序列重复该过程，直到待排序序列有序。
2.快速排序的实现
前面说过，快速排序是一种类似于二叉树结构的排序方式，也就说明，快速排序可以通过递归来实现，从上面的图片可以看出，递归实现快速排序可以使用二叉树的前序遍历的方式。
于是，我们可以这样实现快速排序：
- 说明一下，下面代码只是见一见快排的样子，还没有完全实现。
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
int keyi = PartSort(a, begin, end);
// [begin, keyi-1] keyi [keyi+1, end]
QuickSort2(a, begin, keyi - 1);
QuickSort2(a, keyi + 1, end);
}
- begin > end的时候，说明区间不存在；begin == end的时候，说明待排序序列中只有一个值；此时，都可以直接返回。
- PartSort函数根据基准值完成左右子序列的划分，并将基准值存放在正确的位置上。
- 然后递归左子序列，再递归右子序列，完成同样的功能。
那么，实现快速排序的重点就放在这个PartSort函数上面了，也就是如何根据基准值将区间划分成左右子区间。
基准值的选取一般为待排序区间的最左侧元素。
左右子区间的划分常见的有这三种方式：hoare版、挖坑法、前后指针法。
hoare版
hoare版步骤如下：
- 选取待排序序列的最左侧为基准值。
- 从右边开始找小于基准值的元素。
- 从左边找大于基准值的元素。
- 找到这两个元素之后，交换这两个元素的值。
- 当left和right相遇的时候，交换相遇位置和基准值所在位置的值，并返回基准值。
代码如下：
int PartSort1(int* a, int left, int right)
{
// 选取待排序序列的最左侧为基准值
int keyi = left;
while (left < right)
{
// 找小
while (left < right && a[right] >= a[keyi])
{
--right;
}
// 找大
while (left < right && a[left] <= a[keyi])
{
++left;
}
// 交换这两个元素
Swap(&a[left], &a[right]);
}
// 将left和right相遇位置的元素和基准值交换
Swap(&a[keyi], &a[left]);
// 返回left和right相遇的位置
return left;
}挖坑法
挖坑法步骤如下：
- 选取待排序序列最左侧的元素为基准值，保存基准值，此时基准值所在位置形成坑。
- 从右侧开始找小于基准值的元素，找到之后，将该值放入坑中，该位置形成新的坑。
- 从左侧找大于基准值的元素，找到之后，将该值放入坑中，该位置形参新的坑。
- 重复2、3过程，直到 left 和 right 相遇。
- 相遇之后， 将保存的基准值放入相遇位置，并返回相遇位置。
挖坑法代码如下：
int PartSort2(int* a, int left, int right)
{
// 保存key值以后，左边形成第一个坑
int key = a[left];
int hole = left;
while (left < right)
{
// 右边先走，找小，填到左边的坑，右边形成新的坑位
while (left < right && a[right] >= key)
{
--right;
}
a[hole] = a[right];
hole = right;
// 左边再走，找大，填到右边的坑，左边形成新的坑位
while (left < right && a[left] <= key)
{
++left;
}
a[hole] = a[left];
hole = left;
}
// 将保存的基准值放入相遇位置
a[hole] = key;
// 返回相遇位置
return hole;
}前后指针法
前后指针法步骤如下：
- 选定最左侧元素为基准值并保存，将prev设置为left，cur设置为left+1。
- cur去寻找当前区间内比基准值小的元素
- 如果没找到，说明基准值右侧的元素都是大于基准值的，不需要其他操作，直接跳出循环即可。
- 如果找到了先++prev，再将prev和cur位置的元素交换，然后++cur。
- 等到cur越界之后，说明遍历完序列中的所有元素了，将基准值位置的元素和prev位置的元素交换。
- 最后返回prev即可。
前后指针法能够保证 left+1 ~ prev 的所有元素都是小于基准值的，prev+1 ~ right 的所有元素都是大于基准值的。
前后指针法代码如下：
// 前后指针法
int PartSort3(int* arr, int left, int right)
{
int prev = left;
int cur = prev+1; // cur找小，找到小的就交换
int tmp = arr[left];
while(cur <= right)
{
// cur找到比基准值tmp小的元素or越界才停下来
while(cur <= right && arr[cur] >= tmp)
{
cur++;
}
if(cur > right) // 找不到小的
{
break;
}
else // 找到小的
{
prev++;
swap(&arr[prev], &arr[cur]);
cur++;
}
}
swap(&arr[left], &arr[prev]);
return prev;
}快排代码汇总
当我们实现了三个版本的划分左右子区间的代码之后，我们的快速排序就可以这样写了。
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
int keyi = PartSort1(a, begin, end);
//int keyi = PartSort2(a, begin, end);
//int keyi = PartSort3(a, begin, end);
QuickSort2(a, begin, keyi - 1);
QuickSort2(a, keyi + 1, end);
}当我们想使用不同的划分区间的方法时，只需要放开对应的函数即可。
3.快速排序的优化
三数取中
在前面的代码中，我们都是选取待排序序列的最左侧元素为基准值，这种选取基准值的方法存在缺陷，比如：待排序的序列为有序or接近有序时，在这种情况下，我们每次选取最左侧元素为基准值之后，然后从右侧开始寻找小于基准值的元素，需要一直遍历到基准值的左侧，这个时候的时间复杂度就是O(N^2)了。所以，我们需要改变获取基准值的方式。
这个时候就有人提出三数取中，解决待排序序列为有序or接近有序的情况下，快排效率退化成O(N^2)的缺陷。
// 三数取中
int GetMidi(int* a, int left, int right)
{
int mid = (left + right) / 2;
// left mid right
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right]) // mid是最大值
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right]) // mid是最小
{
return left;
}
else
{
return right;
}
}
}
问题来了，那我们的快排代码是不是要重新写呢？这是不需要的，我们只需要修改即可，也就是在三个版本的划分左右子序列函数中最开始添加这两行代码即可。
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);以hoare版为例：
- 三数取中指的是待排序序列最左侧元素、中间元素、最右侧元素三个元素取中间值。
- 取到中间值之后，将中间值和最左侧元素交换，所以我们选取的还是最左侧元素为基准值，但是本质已经发生变化了。
int PartSort1(int* a, int left, int right)
{
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
// 选取待排序序列的最左侧为基准值
int keyi = left;
while (left < right)
{
// 找小
while (left < right && a[right] >= a[keyi])
{
--right;
}
// 找大
while (left < right && a[left] <= a[keyi])
{
++left;
}
// 交换这两个元素
Swap(&a[left], &a[right]);
}
// 将left和right相遇位置的元素和基准值交换
Swap(&a[keyi], &a[left]);
// 返回left和right相遇的位置
return left;
}小区间优化
前面我们讨论过，递归版的快速排序是类似于二叉树结构的。快速排序的实现在理想情况下是一颗完全二叉树结构，完全二叉树有一个特点是最后一层的结点个数占了整棵树的一半左右，这就意味着，在最后一层我们需要进行的递归次数占了整个排序过程的一半左右。
况且，经过前面的多次递归划分左右子序列并排序，待排序的序列已经变得比较有序了，这个时候我们可以考虑换一种排序方式。
我们都知道，插入排序在待排序序列为有序or接近有序的情况下，排序的时间复杂度为O(N)，所以，当待排序序列的区间比较小的时候，我们可以考虑使用插入排序，减少递归的次数。
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
// 小区间优化，小区间不再递归分割排序，降低递归次数
if ((end - begin + 1) > 20)
{
int keyi = PartSort3(a, begin, end);
// [begin, keyi-1] keyi [keyi+1, end]
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi + 1, end);
}
else
{
InsertSort(a + begin, end - begin + 1);
}
}
三路划分
上面，我们已经使用三数取中来解决了待排序序列在有序or接近有序的情况下时间复杂度退化成O(N^2)的问题；但是，三数取中还有一种不能解决的情况，就是待排序序列全部为重复一样的值or接近全部重复一样，在这种情况下，三数取中每次取出的值和原来待排序序列最左侧的值是一样的，或者说，不管用不用三数取中，每次取出的基准值都有非常大的概率和待排序序列最左侧元素相同。
在这种情况下，将一个待排序序列划分为左右子序列的时间复杂度为O(N)，并且在这种情况下right会一直减小到和left相遇，此时，划分出的左区间待排序元素个数为0，划分出的右区间待排序元素个数为 n-1，比上一层待排序序列个数减少一个，再次进行划分左右子序列的时候，依然会是上面这种情况。
- 在这种情况下，我们可以计算出大概的基本操作的次数是一个等差数列，1+2+3+……+n == (1+n)*n / 2，使用大O表示法表示出来为O(N^2)。
针对这种情况，有人提出了三路划分来解决。
三路划分的步骤如下：
- 选取待排序序列的最左侧为基准值，当然，我们可以使用三数取中来选取基准值。
- L指向最左侧的元素，R指向最右侧的元素，C指向L的后一个元素。
- 然后让C遍历待排序序列，此时会出现以下几种情况：
- C位置的值小于基准值，交换C和L位置的值，然后++C，++L。
- C位置的值等于基准值，++C。
- C位置的值大于基准值，交换C和R位置的值，然后--R。
举个例子：
- 假如有n个元素，可以看出：[0，L-1]之间的元素都是小于基准值的，[L+1，R]之间的元素都是等于基准值的，[R+1，n-1] 之间的元素都是大于基准值的。
采用三路划分优化之后的代码如下：
void QuickSort(int *a, int left, int right)
{
if(left >= right)
{
return;
}
int begin = left;
int end = right;
//三数取中
int midi = GetMidi(a,left,right);
swap(&a[left],&a[midi]);
int cur = left+1;
int key = a[left];
//三路划分
while(cur <= right)
{
if(a[cur] < key)
{
swap(&a[cur], &a[left]);
++left;
++cur;
}
else if(a[cur] > key)
{
swap(&a[right], &a[cur]);
right--;
}
else
{
++cur;
}
}
// [begin, left-1][left,right][right+1,end]
QuickSort(a,begin,left-1);
QuickSort(a,right+1,end);
}有了三路划分之后，面对全部重复元素的时候，遍历一次之后，划分不出左右子区间，排序自然就结束了，避免了大量无效判断。
4.快速排序的非递归版本
快排非递归步骤如下：
- 实现快速排序的非递归版本需要借助栈来实现，先将 end 和 begin 入栈，然后从栈中取两个元素，取出的分别是begin和end，也就是待排序区间。
- 排完之后，根据返回值划分左右子序列，左边的子序列区间为 left ~ keyi-1，右边的子序列区间为 keyi+1 ~ right。
- 然后先将右边的子序列的区间入栈，再将左边的子序列的区间入栈；入的时候先入区间的右边界，再入区间的左边界。
- 每次从栈中取出元素的时候，就能模拟递归的过程来实现快速排序。
快排非递归代码如下：
void QuickSortNonR(int* a, int begin, int end)
{
ST st;
STInit(&st);
// 先入end再入begin，取的时候就是先取begin再取end。
STPush(&st, end);
STPush(&st, begin);
while (!STEmpty(&st))
{
int left = STTop(&st);
STPop(&st);
int right = STTop(&st);
STPop(&st);
int keyi = PartSort1(a, left, right);
// [lefy,keyi-1] keyi [keyi+1, right]
if (keyi+1 < right)
{
STPush(&st, right);
STPush(&st, keyi+1);
}
if (left < keyi-1)
{
STPush(&st, keyi-1);
STPush(&st, left);
}
}
STDestroy(&st);
}5.快速排序总结
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序。
- 时间复杂度：O(N*logN)。每一层遍历n次，最多logN层。
- 空间复杂度：O(logN)。因为，每一层递归需要开辟栈区的空间，最多开辟logN层。
- 稳定性：不稳定，如下图所示。
