快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
1.hoare版本
简单来说就是选某个元素为基准值（这里先默认第一个），然后把比基准值小的都放到基准值的左边，比基准值大的都放到基准值的右边
以下图为例
先以6为基准
然后左边找大，右边找小，之后互换
进行这么一趟后，6左边就都比它小，右边都比它大
然后以6为分界线，再分成两个区间，类似于二叉树
void QuickSort(int* a, int left, int right) {
if (left >= right)
return;//区间不存在时直接返回
int keyi=left;
int begin=left,end=right;
while (begin < end) {
// 从右向左找小于基准的值
while (begin < end && a[end] >= a[keyi])
{
end--;
}
// 从左向右找大于基准的值
while (begin < end && a[begin] <= a[keyi])
{
begin++;
}
Swap(&a[begin], &a[end]);
}
// 将基准放到正确位置
Swap(&a[keyi], &a[end]);
// 递归排序子数组
QuickSort(a, left, end - 1);
QuickSort(a, end + 1, right);
}
}
算法优化
虽然基本快速排序已经很快，但在某些情况下性能会下降，特别是当输入数组已经有序或接近有序时。以下是两种常见的优化策略：
三数取中法
当数组已经有序或接近有序时，选择第一个元素作为基准会导致分区极度不平衡，从而使算法退化为 O(n²) 的时间复杂度。三数取中法通过选择左端、中间和右端三个元素的中值作为基准，可以有效避免这种最坏情况。
三数取中代码如下
int GetMidi(int* a, int left, int right)//左边作key 右边先走
{
int midi = (left + right) / 2;
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
//说明midi是中间值
return midi;
}
//走到这说明midi最大，所以剩下两个数中大的就是中间值
else if(a[left]>a[right])
{
return left;
}
else//剩下最后一种情况 不必多说
{
return right;
}
}
else//走到这说明 a[left]>a[midi]
{
if (a[midi] > a[right])
{
return midi;
}
//到这说明midi最小 所以找剩下两个小的
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
小区间优化
区间比较小时，递归代价比较大，所以要进行小区间优化
对于递归来说
最后一层递归次数占总体的50%，倒数第二层25% ，所以进行小区间优化可以减少递归次数
//区间比较小时。进行小区间优化，不再递归分割排序。减少递归次数
if ((right - left + 1) < 10)
{
InsertSort(a + left, right - left + 1);
}
完整代码如下
#include<stdio.h>
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void InsertSort(int* a, int n)
{
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
//面试手撕快排 不用写小区间优化和三数取中 后续讲一下思路即可 不然会觉得你写的慢
//避免有序情况下效率降低
//1.随机数
//2。三数取中
int GetMidi(int* a, int left, int right)//左边作key 右边先走
{
int midi = (left + right) / 2;
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
//说明midi是中间值
return midi;
}
//走到这说明midi最大，所以剩下两个数中大的就是中间值
else if(a[left]>a[right])
{
return left;
}
else//剩下最后一种情况 不必多说
{
return right;
}
}
else//走到这说明 a[left]>a[midi]
{
if (a[midi] > a[right])
{
return midi;
}
//到这说明midi最小 所以找剩下两个小的
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
void QuickSort(int* a, int left, int right) {
if (left >= right) return;
//小区间优化，不再递归分割排序。减少递归次数
if ((right - left + 1) < 10)
{
InsertSort(a + left, right - left + 1);
}
else
{
//三数取中
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int begin = left + 1; // 从基准下一个开始
int end = right;
while (begin <= end) {
// 从右向左找小于基准的值
while (begin <= end && a[end] >= a[keyi])
end--;
// 从左向右找大于基准的值
while (begin <= end && a[begin] <= a[keyi])
begin++;
// 交换找到的不符合元素
if (begin < end)
Swap(&a[begin], &a[end]);
}
// 将基准放到正确位置
Swap(&a[keyi], &a[end]);
// 递归排序子数组
QuickSort(a, left, end - 1);
QuickSort(a, end + 1, right);
}
}
int main() {
int arr[3] = { 2, 1, 3 };
QuickSort(arr, 0, 2);
for (int i = 0; i < 3; i++) {
printf("%d ", arr[i]); // 输出：1 2 3
}
return 0;
}
为什么要右边先走呢
分析如下图
算法分析
时间复杂度
O(n log n)：一共有logn层递归 每一层都是所有子数组加起来都是n
空间复杂度
- 最佳情况：O(log n) - 递归调用的栈空间
- 最坏情况：O(n) - 当分区极度不平衡时
2.前后指针法
前后指针法是快速排序的另一种常见实现方式，通过两个指针prev和cur来遍历数组，将小于基准值的元素移动到前面。
排序过程
- 定义两个指针prev和cur，prev指向left，cur指向prev+1。
- cur指针向右移动，如果a[cur]小于基准值，则prev++并交换a[prev]和a[cur]。
- 最后将基准值交换到prev位置。
排序一趟的代码如下
int prev = left;
int cur = prev+1;
while(cur<=right)
{
if(a[cur]<a[keyi]&&++prev!=cur)//cur比基准小就交换
Swap(&a[prev],&a[cur])
//cur不管交换还是不交换，都要继续走
cur++
}
Swap(&a[prev],&a[keyi]);
return prev;
完整代码
int PartSort2(int* a, int left, int right)
{
// 三数取中
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int prev = left;
int cur = prev+1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = PartSort1(a, left, right);
// [left, keyi-1] keyi [keyi+1, right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
3.非递归（栈模拟）
递归实现虽然简洁，但在处理大规模数据时可能导致栈溢出。非递归实现通过显式栈来模拟递归过程，避免递归带来的栈开销。
实现思路
- 初始化一个栈，将初始左右下标入栈（先右后左）。
- 循环取出栈顶的左右下标，进行分区操作。
- 将分区后的左右子数组下标入栈，继续处理直到栈为空。
void QuickSortNonR(int* a, int left, int right)
{
ST st;
STInit(&st);
STPush(&st, right);//先入右 再入左
STPush(&st, left);
while (!STEmpty(&st))
{
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
int keyi = PartSort2(a, begin, end);
// [begin, keyi-1] keyi [keyi+1, end]
if (keyi + 1 < end)
{
STPush(&st, end);
STPush(&st, keyi+1);
}
if (begin < keyi-1)
{
STPush(&st, keyi-1);
STPush(&st, begin);
}
}
STDestroy(&st);
}
总结
快速排序是一种高效且应用广泛的排序算法，通过分治策略将问题分解为子问题处理。其性能取决于基准值的选择是否合理，因此在实际应用中常采用三数取中等优化策略来避免最坏情况的发生。
无论是递归还是非递归实现，快速排序都能在平均情况下达到O(n log n)的时间复杂度，使其成为处理大规模数据的理想选择之一