基准值的选定

我们之前已经用四种不同的方式实现了快速排序，如果还没有学习过的伙伴们可以看一下这篇文章哦：数据结构之排序大全（3）-CSDN博客

那我们既然已经学习了这么多种方法，为什么还要继续探索快速排序呢？

那是因为我们之前写的排序算法虽然在大部分情况下可以高效率地解决排序问题（效率较高的情况下，递归产生的递归树形状是完全二叉树的结构），时间复杂度是O(n*logN）但是在一些极端的情况下，算法的时间复杂度会退化成O(N^2)。这是咋回事呢？

我们在上面的博客中已经举过一个例子：当数组已经处于排好序的状态时，形成的递归深度h=n，这句会导致时间复杂度退化成O(N^2)。

这是因为我们指定了最左边的数作为基准值，而当数组已经有序时，每次选择最左边元素作为基准值会导致分区极度不平衡，一边永远为空，另一边包含所有剩余元素，使得递归深度从 O(log n) 退化为 O(n)，时间复杂度从 O(n log n) 退化为 O(n²)。对已排序的数组，选最左基准值会导致快速排序退化成冒泡排序，每次只能处理一个元素。

上面问题的发生就是因为我们选基准值选的不太好，有没有什么解决方法呢？

当然是有的，既然根本原因就是我们的基准值选的不好，那我们就重新选定基准值就好了呀。

随机选定基准值当然可以使用生成随机数的函数：

int randi = left + (rand() % (right-left + 1));

这个公式是怎么来的呢？

我们知道任意一个数模除x的范围在0~x-1，那么任意一个数模除x+1的范围就在0~x之间，那么任意一个数模除right-left+1的范围就在0~right-left之间，那么left+rand()%(right-left+1)的范围就在left~right之间。

如果我们要在代码中使用随机数位置的数值作为基准值，那就将代码写成：

#include<stdlib.h>
#include<time.h>//交换元素
void swap(int* px, int* py)
{int tmp = *px;*px = *py;*py = tmp;
}//指定基准值，将基准值放到对应的位置，函数会返回基准值的下标
int _QuickSort_Hoare(int* arr, int left, int right)
{int randi =left+rand()%(right-left+1)swap(&arr[randi], &arr[left]);//指定基准值为左端点位置上的数int keyi = left;//left从左往右走，找比基准值大的数//keyi初始与left指向相同，不妨就先让left向右走一步left++;//right从右往左走，找比基准值小的数while (left <= right){//在right和left移动的过程中始终要满足left<=rightwhile (left <= right && arr[left] < arr[keyi]){left++;}while (left <= right && arr[right] > arr[keyi]){right--;}//走到这一步,有两种可能：//1)   left>right//2）left<=right并且left指向的值大于arr[keyi]，right指向的值小于arr[keyi]if (left <= right){swap(&arr[left], &arr[right]);left++;right--;}}//此时left>right（left=right+1),那么就有right以及right前面的位置所存放的值都小于arr[keyi]//left以及left后面的位置所存放的值都大于arr[keyi]swap(&arr[keyi], &arr[right]);keyi = right;return keyi;
}int _QuickSort_Hole(int* arr, int left, int right)
{int randi =left+rand()%(right-left+1)swap(&arr[randi], &arr[left]);//指定基准值int key = arr[left];//挖坑int hole = left;while (left < right){//right从右往左找比基准值要小的while (left < right && arr[right] >= key){right--;}//将right位置存放的值拿去填坑arr[hole] = arr[right];//更新坑位hole = right;//left从左往右找比基准值大的while (left < right && arr[left] <= key){left++;}//将left位置存放的值拿去填坑arr[hole] = arr[left];//更新坑位hole = left;}//跳出循环，必有left==right，此时left和right都指向坑位hole//而hole就是基准值应该在的位置//用基准值填最后一个坑arr[hole] = key;return hole;
}int _QuickSort_lomuto(int* arr, int left, int right)
{int randi =left+rand()%(right-left+1)swap(&arr[randi], &arr[left]);int keyi = left;int prev = left;int pcur = prev + 1;while (pcur <= right){if (arr[pcur] < arr[keyi] && ++prev != pcur){swap(&arr[prev], &arr[pcur]);}pcur++;}//走到最后，prev的位置就是基准值应该存放的位置swap(&arr[prev], &arr[keyi]);return prev;
}//快速排序
//left表示序列的左端点下标  right表示序列的右端点下标
void QuickSort(int* arr, int left, int right)
{srand((unsigned int)time(NULL));if (left >= right)//左端点>=右端点，说明这个序列中已经有序{return;}//找基准值keyiint keyi = _QuickSort_lomuto(arr, left, right);//找到基准值后，将序列划分：left  keyi   rightQuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);}

但是，我们使用随机值在极端情况下也会不可避免的出现上面的问题，那还有没有别的方法呢？

且看下面分解：

三数取中找基准值

我们要找一个基准值，使根据算法给基准值找到它应该在的位置的时候，我们可以根据基准值所在的位置将整个序列基本均分，那么我们找的基准值至少不能是序列中最大或者最小的值，这样的话，我们就可以比较序列中左端点，右端点以及中间端点的值，找出这三个数中的中间值，如果用这个中间值来作为基准值，那么这个基准值一定不是整个序列中最大值或最小值,整个思路比较简单，我们来写一下代码：

//三数取中
int GetMid(int* arr, int left, int right)
{int midi = (left + right) / 2;if (arr[left] < arr[midi]){if (arr[midi] < arr[right]){return  midi;}else if (arr[left] < arr[right]){return right;}else{return left;}}else//arr[left]>=arr[mid]{if (arr[midi] > arr[right]){return midi;}else if (arr[right] < arr[left]){return right;}else{return left;}}
}

我们接下来就利用一下这个代码，在此之前，我们先用以下代码测试一下原来快速排序对10万个元素的有序序列进行排序的性能：

//test.c
#define  _CRT_SECURE_NO_WARNINGS 1
#include"sort.h"
// 测试排序的性能对⽐
void TestOP()
{//生成随机数，将随机数存入数组srand((unsigned int)time(0));const int N = 100000;int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a4[i] = rand();a5[i] = a4[i];}int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a4, 0, N - 1);int end5 = clock();printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);free(a4);free(a5);}int main()
{TestOP();return 0;
}

//sort.h
#pragma once#include<stdio.h>
#include<stdlib.h>
#include<time.h>//快速排序
void QuickSort(int* arr, int left, int right);//堆排序
void HeapSort(int* arr, int n);

//sort.c#define  _CRT_SECURE_NO_WARNINGS 1
#include"sort.h"
//交换元素
void swap(int* px, int* py)
{int tmp = *px;*px = *py;*py = tmp;
}//堆排序
//向下调整算法
void AdjustDown(int* arr, int n, int parent)
{int child = 2 * parent + 1;while (child < n){if (child + 1 < n && arr[child] < arr[child + 1])//此时默认是建立大堆{child++;}if (arr[parent] < arr[child]){swap(&arr[parent], &arr[child]);parent = child;child = 2 * parent + 1;}else{break;}}
}
void HeapSort(int* arr, int n)
{//先将元素建堆——利用向下调整算法//升序建大堆，降序建小堆//这里我们就选择排升序for (int parent = (n - 1 - 1) / 2; parent >= 0; parent--){AdjustDown(arr, n, parent);}//建完堆以后，利用堆结构进行排序for (int size = n - 1; size > 0; size--){swap(&arr[0], &arr[size]);//对剩下的size个元素进行向下调整AdjustDown(arr, size, 0);}
}//指定基准值，将基准值放到对应的位置，函数会返回基准值的下标
int _QuickSort_Hoare(int* arr, int left, int right)
{//指定基准值为左端点位置上的数int keyi = left;//left从左往右走，找比基准值大的数//keyi初始与left指向相同，不妨就先让left向右走一步left++;//right从右往左走，找比基准值小的数while (left <= right){//在right和left移动的过程中始终要满足left<=rightwhile (left <= right && arr[left] < arr[keyi]){left++;}while (left <= right && arr[right] > arr[keyi]){right--;}//走到这一步,有两种可能：//1)   left>right//2）left<=right并且left指向的值大于arr[keyi]，right指向的值小于arr[keyi]if (left <= right){swap(&arr[left], &arr[right]);left++;right--;}}//此时left>right（left=right+1),那么就有right以及right前面的位置所存放的值都小于arr[keyi]//left以及left后面的位置所存放的值都大于arr[keyi]swap(&arr[keyi], &arr[right]);keyi = right;return keyi;
}int _QuickSort_Hole(int* arr, int left, int right)
{//指定基准值int key = arr[left];//挖坑int hole = left;while (left < right){//right从右往左找比基准值要小的while (left < right && arr[right] >= key){right--;}//将right位置存放的值拿去填坑arr[hole] = arr[right];//更新坑位hole = right;//left从左往右找比基准值大的while (left < right && arr[left] <= key){left++;}//将left位置存放的值拿去填坑arr[hole] = arr[left];//更新坑位hole = left;}//跳出循环，必有left==right，此时left和right都指向坑位hole//而hole就是基准值应该在的位置//用基准值填最后一个坑arr[hole] = key;return hole;
}int _QuickSort_lomuto(int* arr, int left, int right)
{int keyi = left;int prev = left;int pcur = prev + 1;while (pcur <= right){if (arr[pcur] < arr[keyi] && ++prev != pcur){swap(&arr[prev], &arr[pcur]);}pcur++;}//走到最后，prev的位置就是基准值应该存放的位置swap(&arr[prev], &arr[keyi]);return prev;
}//快速排序
//left表示序列的左端点下标  right表示序列的右端点下标
void QuickSort(int* arr, int left, int right)
{if (left >= right)//左端点>=右端点，说明这个序列中已经有序{return;}//找基准值keyiint keyi = _QuickSort_lomuto(arr, left, right);//找到基准值后，将序列划分：left  keyi   rightQuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);}

上面的代码中，我们先利用堆排序使得10万个数据有序，然后再用快速排序对这10万个数据进行排序,看一下效果：

测试环境：Debug,x86

我们可以看到，代码崩溃了，这真的很令人奇怪了，注意哦，小编这里已经用较小的数据集合对代码测试过了，代码运行是没有问题的。

Debug版本包含了许多调试信息，而Release版本的代码就进行了较多的优化，我们要不试试release版本呢？

运行结果：

可以看到，release版本下我们的代码可以正常运行，说明我们的代码本身并没有错误，而且我们可以看到快速排序的时间性能比起堆排序慢的太多了。

我们在通过调试过程看一下为什么在Debug版本下代码崩溃了：

我们可以看到，调用堆栈的层次很深，代码之所以崩溃是因为递归层次太深导致栈溢出了，这也是快速排序在对有序数组排序过程中的致命弱点。

那我们来试一试优化以后的快速排序呢：

//交换元素
void swap(int* px, int* py)
{int tmp = *px;*px = *py;*py = tmp;
}//三数取中
int GetMid(int* arr, int left, int right)
{int midi = (left + right) / 2;if (arr[left] < arr[midi]){if (arr[midi] < arr[right]){return  midi;}else if (arr[left] < arr[right]){return right;}else{return left;}}else//arr[left]>=arr[mid]{if (arr[midi] > arr[right]){return midi;}else if (arr[right] < arr[left]){return right;}else{return left;}}
}//指定基准值，将基准值放到对应的位置，函数会返回基准值的下标
int _QuickSort_Hoare(int* arr, int left, int right)
{int midi = GetMid(arr, left, right);swap(&arr[midi], &arr[left]);//指定基准值为左端点位置上的数int keyi = left;//left从左往右走，找比基准值大的数//keyi初始与left指向相同，不妨就先让left向右走一步left++;//right从右往左走，找比基准值小的数while (left <= right){//在right和left移动的过程中始终要满足left<=rightwhile (left <= right && arr[left] < arr[keyi]){left++;}while (left <= right && arr[right] > arr[keyi]){right--;}//走到这一步,有两种可能：//1)   left>right//2）left<=right并且left指向的值大于arr[keyi]，right指向的值小于arr[keyi]if (left <= right){swap(&arr[left], &arr[right]);left++;right--;}}//此时left>right（left=right+1),那么就有right以及right前面的位置所存放的值都小于arr[keyi]//left以及left后面的位置所存放的值都大于arr[keyi]swap(&arr[keyi], &arr[right]);keyi = right;return keyi;
}int _QuickSort_Hole(int* arr, int left, int right)
{int midi = GetMid(arr, left, right);swap(&arr[midi], &arr[left]);//指定基准值int key = arr[left];//挖坑int hole = left;while (left < right){//right从右往左找比基准值要小的while (left < right && arr[right] >= key){right--;}//将right位置存放的值拿去填坑arr[hole] = arr[right];//更新坑位hole = right;//left从左往右找比基准值大的while (left < right && arr[left] <= key){left++;}//将left位置存放的值拿去填坑arr[hole] = arr[left];//更新坑位hole = left;}//跳出循环，必有left==right，此时left和right都指向坑位hole//而hole就是基准值应该在的位置//用基准值填最后一个坑arr[hole] = key;return hole;
}int _QuickSort_lomuto(int* arr, int left, int right)
{int midi = GetMid(arr, left, right);swap(&arr[midi], &arr[left]);int keyi = left;int prev = left;int pcur = prev + 1;while (pcur <= right){if (arr[pcur] < arr[keyi] && ++prev != pcur){swap(&arr[prev], &arr[pcur]);}pcur++;}//走到最后，prev的位置就是基准值应该存放的位置swap(&arr[prev], &arr[keyi]);return prev;
}//快速排序
//left表示序列的左端点下标  right表示序列的右端点下标
void QuickSort(int* arr, int left, int right)
{if (left >= right)//左端点>=右端点，说明这个序列中已经有序{return;}//找基准值keyiint keyi = _QuickSort_lomuto(arr, left, right);//找到基准值后，将序列划分：left  keyi   rightQuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);}

我们只是在每个算法的里面加上了前面两句代码，重新指定基准值，其他逻辑全都不变，现在，我们再来测试一下算法：

测试环境：Debug，可以看到快速排序在排序有序数组时的时间性能确实提高了。

快速排序的小区间优化

当快速排序递归到小区间时（通常是 10-20个元素），使用插入排序而不是继续递归，这种优化称为小区间优化。

 为什么要优化？

递归的成本：

• 函数调用开销：每次递归调用都需要创建栈帧、保存寄存器、传递参数等

• 栈空间消耗：深度递归可能导致栈溢出

• 缓存不友好：频繁的函数调用破坏缓存局部性

插入排序的优势：

• 小数据量高效：当 n < 15 时，插入排序的实际性能比快速排序更好

• 简单直接：没有函数调用开销

• 常数因子小：实际运行时间更少

插入排序我们之前已经写过了，那我们现在就来直接写一下优化后的代码：

//交换元素
void swap(int* px, int* py)
{int tmp = *px;*px = *py;*py = tmp;
}
//三数取中
int GetMid(int* arr, int left, int right)
{int midi = (left + right) / 2;if (arr[left] < arr[midi]){if (arr[midi] < arr[right]){return  midi;}else if (arr[left] < arr[right]){return right;}else{return left;}}else//arr[left]>=arr[mid]{if (arr[midi] > arr[right]){return midi;}else if (arr[right] < arr[left]){return right;}else{return left;}}
}//直接插入排序
void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int end = i;//end表示已经排好序列的最后一个元素的下标，初始已经排好的序列中只有一个元素//这个元素就是数组中的第一个元素，下标是0
//循环将end的下一个元素放到已经排好序的序列中int tmp = arr[end + 1];while (end >= 0){//找到tmp应该放在的位置if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}//指定基准值，将基准值放到对应的位置，函数会返回基准值的下标
int _QuickSort_Hoare(int* arr, int left, int right)
{int midi = GetMid(arr, left, right);swap(&arr[midi], &arr[left]);//指定基准值为左端点位置上的数int keyi = left;//left从左往右走，找比基准值大的数//keyi初始与left指向相同，不妨就先让left向右走一步left++;//right从右往左走，找比基准值小的数while (left <= right){//在right和left移动的过程中始终要满足left<=rightwhile (left <= right && arr[left] < arr[keyi]){left++;}while (left <= right && arr[right] > arr[keyi]){right--;}//走到这一步,有两种可能：//1)   left>right//2）left<=right并且left指向的值大于arr[keyi]，right指向的值小于arr[keyi]if (left <= right){swap(&arr[left], &arr[right]);left++;right--;}}//此时left>right（left=right+1),那么就有right以及right前面的位置所存放的值都小于arr[keyi]//left以及left后面的位置所存放的值都大于arr[keyi]swap(&arr[keyi], &arr[right]);keyi = right;return keyi;
}int _QuickSort_Hole(int* arr, int left, int right)
{int midi = GetMid(arr, left, right);swap(&arr[midi], &arr[left]);//指定基准值int key = arr[left];//挖坑int hole = left;while (left < right){//right从右往左找比基准值要小的while (left < right && arr[right] >= key){right--;}//将right位置存放的值拿去填坑arr[hole] = arr[right];//更新坑位hole = right;//left从左往右找比基准值大的while (left < right && arr[left] <= key){left++;}//将left位置存放的值拿去填坑arr[hole] = arr[left];//更新坑位hole = left;}//跳出循环，必有left==right，此时left和right都指向坑位hole//而hole就是基准值应该在的位置//用基准值填最后一个坑arr[hole] = key;return hole;
}int _QuickSort_lomuto(int* arr, int left, int right)
{int midi = GetMid(arr, left, right);swap(&arr[midi], &arr[left]);int keyi = left;int prev = left;int pcur = prev + 1;while (pcur <= right){if (arr[pcur] < arr[keyi] && ++prev != pcur){swap(&arr[prev], &arr[pcur]);}pcur++;}//走到最后，prev的位置就是基准值应该存放的位置swap(&arr[prev], &arr[keyi]);return prev;
}//快速排序
//left表示序列的左端点下标  right表示序列的右端点下标
void QuickSort(int* arr, int left, int right)
{if (left >= right)//左端点>=右端点，说明这个序列中已经有序{return;}if (right - left + 1 < 10)//小区间优化，不再递归分割排序，减少递归次数，直接使用插入排序{//插入排序的第一个参数时待排序列的起始地址，待排序列的区间是[left,right],//所以待排序列的起始地址是arr+leftInsertSort(arr+left, right - left + 1);}else{//找基准值keyiint keyi = _QuickSort_lomuto(arr, left, right);//找到基准值后，将序列划分：left  keyi   rightQuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);}}

快速排序之三路划分

虽然上面的代码解决了，但对于下面的情况还是不能达到优化效果：

现在小编就再用前面讲的lomuto双指针法来举一个例子：假设我们要排序的数组长这样：{2,2,2,2,2}，如果利用双指针法，那么递归过程中形成的二叉树的形状：

如图，当数组中都是重复数据时，lomuto双指针法递归产生的二叉树的深度就会变成n，时间复杂度也就退化成了O(N^2)。

那么，有没有什么好的解决办法呢？

既然小编已经提出了，那就一定是有解决办法的，这就是我们这一部分要学的快排的三路划分。

当面对有大量跟 key 相同的值时，三路划分的核心思想有点类似 hoare 的左右指针和 lomuto 的前后指针的结合。核心思想是把数组中的数据分为三段【比 key 小的值】【跟 key 相等的值】【比 key 大的值】，所以叫做三路划分算法。

理解一下实现思想：

1. key 默认取 left 位置的值。
2. left 指向区间最左边，right 指向区间最后边，cur 指向 left+1 位置。
3. cur 遇到比 key 小的值后跟 left 位置交换，换到左边，left++，cur++。
4. cur 遇到比 key 大的值后跟 right 位置交换，换到右边，right--。
5. cur 遇到跟 key 相等的值后，cur++。
6. 直到 cur > right 结束

//三路划分实现快速排序
void QuickSort_ThreeWay(int* arr, int left, int right)
{if (left >= right){return;}//小区间优化//if (right - left + 1 < 10)//{//	InsertSort(arr + left, right - left + 1);//}//else//{//三路划分int midi = GetMid(arr, left, right);swap(&arr[midi], &arr[left]);int key = arr[left];int begin = left, end = right;int cur = left + 1;while (cur <= right){if (arr[cur] < key){swap(&arr[cur], &arr[left]);left++;cur++;}else if (arr[cur] > key){swap(&arr[cur], &arr[right]);right--;}else{cur++;}}//将序列分成了三部分：[begin,left-1]  [left,right]  [right+1,end]//[left,right]区间的数值都等于基准值QuickSort_ThreeWay(arr, begin, left - 1);QuickSort_ThreeWay(arr, right + 1, end);//}
}

快速排序之自省排序

introsort 是 introspective sort 采用了缩写，他的名字其实表达了他的实现思路，他的思路就是进行自我侦测和反省，快排递归深度太深（cpp stl 中使用的是深度为 2 倍排序元素数量的对数值）那就说明在这种数据序列下，选 key 出现了问题，性能在快速退化，那么就不要再进行快排分割递归了，改换为堆排序进行排序。

自省排序的核心思想是：

1. 快速排序为主：处理大多数情况

2. 堆排序为保险：防止快速排序退化

3. 插入排序优化：处理小数据量

4. 智能监控：根据实际情况自动切换算法

这种混合方法实现了：

• ✅ 保持快速排序的平均性能

• ✅ 避免最坏情况下的性能退化

• ✅ 对小数据量有优化效果

• ✅ 在实际应用中表现稳定

排序的基本思想：

实现代码：

//自省排序
void IntroSort(int* arr, int left, int right, int depth, int defaltdepth)
{if (left >= right){return;}// 数组⻓度⼩于16的⼩数组，换为插⼊排序，简单递归次数if (right - left + 1 < 16){InsertSort(arr + left, right - left + 1);return;}//检查是否递归层次太深了if (depth > defaltdepth){HeapSort(arr + left, right - left + 1);return;}depth++;//使用lomuto双指针法int midi = GetMid(arr, left, right);swap(&arr[left], &arr[midi]);int keyi = left;int prev = left, pcur = prev + 1;while (pcur <= right){if (arr[pcur] < arr[keyi] && ++prev != pcur){swap(&arr[pcur], &arr[prev]);}pcur++;}swap(&arr[keyi], &arr[prev]);keyi = prev;//继续递归左右子序列[left,keyi-1][keyi+1,right]IntroSort(arr, left, keyi - 1, depth, defaltdepth);IntroSort(arr,  keyi +1, right,depth, defaltdepth);
}void  QuickSort_(int* arr, int left, int right)
{int depth = 0;int logN = 0;//表示递归深度的阈值int N = right - left + 1;//表示数组元素个数//为什么需要这个logn：//	在自省排序中，当递归深度超过 2 × logn 时，算法会从快速排序切换到堆排序//	这是为了防止快速排序在最坏情况下（如已经有序的数组）退化为 O(n²) 的时间复杂度//	通过限制递归深度，保证最坏情况下的时间复杂度为 O(n log n)//计算递归深度的阈值for (int i = 0; i < N; i *= 2){logN++;}// introspective sort -- ⾃省排序IntroSort(arr, left, right, depth, 2 * logN);
}

小结：本节内容我们深入探索了快速排序的实现方法，这一节将上一篇文章中快速排序的性能问题逐个击破，小编觉得这一节是比较有意思的。同时这一小节的代码量也是超级丰富的，兄弟们一定要自己手动敲一下代码哦！！！

喜欢小编的兄弟们欢迎三连哦，小编会继续更新编程方面的内容的。对于本节内容有任何问题的朋友欢迎在评论区留言哦！！！