🔥个人主页：@草莓熊Lotso
🎬作者简介：C++研发方向学习者
📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》
⭐️人生格言：生活是默默的坚持，毅力是永久的享受。
前言： 在之前的博客中我们实现了递归版本和非递归版本的快速排序，其中递归版本中的找基准的方法我们学习了三种。但是有些特殊的情况，比如重复元素过多或者已经有序的时候，我们的时间效率就会受到影响了，这次的进阶篇中，我们会通过一些方法来优化快速排序
目录
一.三数取中和随机数选择基准
三数取中法：
原理：从子数组的首元素、尾元素、中间元素中选择中位数作为基准。通过选取中间大小的值，避免极端值（如最大/最小值）作为基准，从而平衡左右子数组的划分。
核心逻辑：
- 计算子数组的中间索引 mid = left + (right - left) / 2；
- 比较 arr[left]、arr[mid]、arr[right] 三个元素；
- 将三者中的中位数作为基准，并交换到合适位置。
代码实现：
//三数取中
int threewaymid(int* arr, int left, int right)
{
int mid = (left + right) / 2;
if (arr[left] > arr[right])
{
swap(&arr[left], &arr[right]);
}
if (arr[mid] > arr[right])
{
swap(&arr[mid], &arr[right]);
}
if (arr[mid] < arr[left])
{
swap(&arr[mid], &arr[left]);
}
return mid;
}--注意我这里返回的下标，后续需要在快速排序主体函数里面操作一下
随机数选择法：
原理：从子数组的 [left, right] 范围内随机选择一个元素作为基准。通过随机性避免固定模式导致的最坏情况（如对有序数组排序时总是选首元素作为基准）。
核心逻辑：
- 生成 [left, right] 范围内的随机整数作为基准索引；
- 将随机选中的元素与固定位置交换。
代码实现：(直接在快排主函数里面)
//随机数取法
srand((unsigned int)time(NULL));
int randi = left + rand() % (right - left + 1);
swap(&arr[left], &arr[randi]);两种方法的对比分析 :
实际使用场景建议：
1. 优先选择三数取中：
在多数实际场景（尤其是可能存在部分有序的数据）中，三数取中法的划分平衡性更稳定，且无随机数生成的额外开销，综合性能更优。C语言标准库中的快速排序实现（如qsort）常采用类似优化。
2. 随机数法的补充场景：
当数据分布完全未知或需要避免潜在的“对抗性输入”（如刻意构造的最坏情况数组）时，随机数选择法是更安全的选择。
二.三路划分
前面实现的两个方式是解决如何找key的问题以及数组接近有序的情况，而三路划分主要是用于处理有大量与Key值相同的元素时的情况。
在快速排序中，当数组存在大量重复元素时，传统的二路划分（小于基准/大于基准）会导致分割失衡，效率下降。三路划分 通过将数组分为“小于基准、等于基准、大于基准”三部分，有效解决重复元素问题，提升排序稳定性。
核心逻辑： 将数组划分为3个部分(其中begin和end分别记录left和right的初始位置)
- arr[begin,left-1]，所有元素都小于基准
- arr[left,right]，所有元素都等于基准
- arr[right+1,end]，所有元素都大于基准
实现步骤：
1.选择基准：我们可以采用面的三数取中或者随机数选择法
2.初始化指针：
- begin记录left初始位置
- end记录right初始位置
- cur=left+1，遍历使用的指针
3.遍历和划分：
- 若 arr[cur] < key：交换 arr[cur] 与 arr[left]，left++，cur++（扩展小于区域）
- 若 arr[cur] == key：cur++（直接纳入等于区域）
- 若 arr[cur] > key：交换 arr[cur] 与 arr[right]，right--（扩展大于区域，cur不变，需重新检查交换后的元素）
4.递归处理： 遍历结束后，递归排序arr[begin,left-1]，arr[right+1,end]
代码实现：
//快速排序进阶
//三路划分实现快速排序(结合随机数法或三位取中)--应对大量重复数据和有序的情况
//三数取中
int threewaymid(int* arr, int left, int right)
{
int mid = (left + right) / 2;
if (arr[left] < arr[right])
{
swap(&arr[left], &arr[right]);
}
if (arr[mid] > arr[right])
{
swap(&arr[mid], &arr[right]);
}
if (arr[mid] < arr[left])
{
swap(&arr[mid], &arr[left]);
}
return mid;
}
void QuickSortMore(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
////随机数取法
//srand((unsigned int)time(NULL));
//int randi = left + rand() % (right - left + 1);
//swap(&arr[left], &arr[randi]);
//三数取中
int midi = threewaymid(arr, left, right);
swap(&arr[midi], &arr[left]);
int key = arr[left];
int cur = left + 1;
int begin = left;
int end = right;
while (cur <= right)
{
if (arr[cur] < key)
{
swap(&arr[left], &arr[cur]);
left++;
cur++;
}
else if (arr[cur] > key)
{
swap(&arr[right], &arr[cur]);
right--;
}
else {
cur++;
}
}
//三路划分【begin,left-1】【left,right】【right+1,end】
QuickSortMore(arr, begin, left - 1);
QuickSortMore(arr, right + 1, end);
}
图示如下：
--我们通过上面描述的操作通过画图模拟过程后可以发现，确实能成功的划分出来三个部分，且每个分区的边界都很清晰
三路划分和传统二路划分思路的对比：
总结：三路划分是对传统快排的针对性优化，在重复元素场景下优势明显，而在随机分布的无重复元素场景中，性能与传统快排接近（仅略高常数开销），是一种更通用的快排改进方案。
--这里给大家提供一个测试快排效率的代码，大家可以自己去试试
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
void PrintArray(int* a, int n) {
for (int i = 0; i < n; ++i) {
printf("%d ", a[i]);
}
printf("\n");
}
void Swap(int* p1, int* p2) {
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// hoare
// [left, right]
int PartSort1(int* a, int left, int right) {
int keyi = left;
++left;
while (left <= right) { //left和right相遇的位置的值⽐基准值要⼤
//right找到⽐基准值⼩或等
while (left <= right && a[right] > a[keyi]) {
right--;
}
//left找到⽐基准值⼤或等
while (left <= right && a[left] < a[keyi]) {
left++;
}
//right left
if (left <= right) {
Swap(&a[left++], &a[right--]);
}
}
//right keyi交换
Swap(&a[keyi], &a[right]);
return right;
}
// 前后指针
int PartSort2(int* a, int left, int right) {
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[prev], &a[keyi]);
keyi = prev;
return keyi;
}
typedef struct {
int leftKeyi;
int rightKeyi;
} KeyWayIndex;
// 三路划分
KeyWayIndex PartSort3Way(int* a, int left, int right) {
int key = a[left];
// left和right指向就是跟key相等的区间
// [开始, left-1][left, right][right+1, 结束]
int cur = left + 1;
while (cur <= right) {
// 1、cur遇到⽐key⼩，⼩的换到左边，同时把key换到中间位置
// 2、cur遇到⽐key⼤，⼤的换到右边
if (a[cur] < key) {
Swap(&a[cur], &a[left]);
++cur;
++left;
} else if (a[cur] > key) {
Swap(&a[cur], &a[right]);
--right;
} else {
++cur;
}
}
KeyWayIndex kwi;
kwi.leftKeyi = left;
kwi.rightKeyi = right;
return kwi;
}
void TestPartSort1() {
int a1[] = { 6, 1, 7, 6, 6, 6, 4, 9 };
int a2[] = { 3, 2, 3, 3, 3, 3, 2, 3 };
int a3[] = { 2, 2, 2, 2, 2, 2, 2, 2 };
PrintArray(a1, sizeof(a1) / sizeof(int));
int keyi1 = PartSort1(a1, 0, sizeof(a1) / sizeof(int) - 1);
PrintArray(a1, sizeof(a1) / sizeof(int));
printf("hoare keyi:%d\n\n", keyi1);
PrintArray(a2, sizeof(a2) / sizeof(int));
int keyi2 = PartSort1(a2, 0, sizeof(a2) / sizeof(int) - 1);
PrintArray(a2, sizeof(a2) / sizeof(int));
printf("hoare keyi:%d\n\n", keyi2);
PrintArray(a3, sizeof(a3) / sizeof(int));
int keyi3 = PartSort1(a3, 0, sizeof(a3) / sizeof(int) - 1);
PrintArray(a3, sizeof(a3) / sizeof(int));
printf("hoare keyi:%d\n\n", keyi3);
}
void TestPartSort2() {
int a1[] = { 6, 1, 7, 6, 6, 6, 4, 9 };
int a2[] = { 3, 2, 3, 3, 3, 3, 2, 3 };
int a3[] = { 2, 2, 2, 2, 2, 2, 2, 2 };
PrintArray(a1, sizeof(a1) / sizeof(int));
int keyi1 = PartSort2(a1, 0, sizeof(a1) / sizeof(int) - 1);
PrintArray(a1, sizeof(a1) / sizeof(int));
printf("前后指针 keyi:%d\n\n", keyi1);
PrintArray(a2, sizeof(a2) / sizeof(int));
int keyi2 = PartSort2(a2, 0, sizeof(a2) / sizeof(int) - 1);
PrintArray(a2, sizeof(a2) / sizeof(int));
printf("前后指针 keyi:%d\n\n", keyi2);
PrintArray(a3, sizeof(a3) / sizeof(int));
int keyi3 = PartSort2(a3, 0, sizeof(a3) / sizeof(int) - 1);
PrintArray(a3, sizeof(a3) / sizeof(int));
printf("前后指针 keyi:%d\n\n", keyi3);
}
void TestPartSort3() {
//int a0[] = { 6,1,2,7,9,3,4,5,10,4 };
int a1[] = { 6, 1, 7, 6, 6, 6, 4, 9 };
int a2[] = { 3, 2, 3, 3, 3, 3, 2, 3 };
int a3[] = { 2, 2, 2, 2, 2, 2, 2, 2 };
PrintArray(a1, sizeof(a1) / sizeof(int));
KeyWayIndex kwi1 = PartSort3Way(a1, 0, sizeof(a1) / sizeof(int) - 1);
PrintArray(a1, sizeof(a1) / sizeof(int));
printf("3Way keyi:%d,%d\n\n", kwi1.leftKeyi, kwi1.rightKeyi);
PrintArray(a2, sizeof(a2) / sizeof(int));
KeyWayIndex kwi2 = PartSort3Way(a2, 0, sizeof(a2) / sizeof(int) - 1);
PrintArray(a2, sizeof(a2) / sizeof(int));
printf("3Way keyi:%d,%d\n\n", kwi2.leftKeyi, kwi2.rightKeyi);
PrintArray(a3, sizeof(a3) / sizeof(int));
KeyWayIndex kwi3 = PartSort3Way(a3, 0, sizeof(a3) / sizeof(int) - 1);
PrintArray(a3, sizeof(a3) / sizeof(int));
printf("3Way keyi:%d,%d\n\n", kwi3.leftKeyi, kwi3.rightKeyi);
}
int main() {
TestPartSort1();
TestPartSort2();
TestPartSort3();
return 0;
}
三.自省排序
“自省排序”（Introspective Sort，简称IntroSort）是对快速排序的一种增强优化算法，它结合了快速排序、堆排序和插入排序的优点，通过“自省”（监控排序过程）动态调整排序策略，避免快速排序在极端情况下的性能退化，是一种兼具高效性和稳定性的综合排序方案。
核心思想：
- 初始阶段使用快速排序，利用其在平均情况下的高效性（O(n log n)）；
- 通过监控递归深度，当深度超过阈值（通常为 2×logn)）时，判断可能出现了分割失衡，自动切换为堆排序，避免快排最坏情况的O(n²)时间复杂度；
- 当子数组规模小于阈值（如16）时，切换为插入排序，减少递归和分割的开销。
这种“自省”机制确保了算法在各种数据场景下的稳定性，既保留快排的平均高效性，又通过堆排序兜底最坏情况。
代码实现：
--我这里的部分实现和前面一些示例会有一些差别，但是都是正确的，大家都可以参考实现一下。
#include"introsort.h"
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
// 选出左右孩⼦中⼤的那⼀个
if (child + 1 < n && a[child + 1] > a[child])
{
++child;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
// 建堆 -- 向下调整建堆 -- O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
// 需要自己先实现 -- O(N*logN)
int end = n - 1;
while (end > 0)
{
Swap(&a[end], &a[0]);
AdjustDown(a, end, 0);
--end;
}
}
void InsertSort(int* a, int n)
{
for (int i = 1; i < n; i++)
{
int end = i - 1;
int tmp = a[i];
// 将tmp插⼊到[0,end]区间中，保持有序
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
// 三值取中函数
int MedianOfThree(int* arr, int left, int right)
{
int mid = left + (right - left) / 2;
// 比较并交换，确保 arr[left] <= arr[mid] <= arr[right]
if (arr[left] > arr[mid])
Swap(&arr[left], &arr[mid]);
if (arr[left] > arr[right])
Swap(&arr[left], &arr[right]);
if (arr[mid] > arr[right])
Swap(&arr[mid], &arr[right]);
// 使用中间值作为基准值，并将其移到 left 位置
Swap(&arr[left], &arr[mid]);
return arr[left]; // 返回基准值
}
void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{
if (left >= right)
return;
// 数组⻓度小于16的小数组，换为插入排序，简单递归次数
if (right - left + 1 < 16)
{
InsertSort(a + left, right - left + 1);
return;
}
// 当深度超过2*logN时改用堆排序
if (depth > defaultDepth)
{
HeapSort(a + left, right - left + 1);
return;
}
depth++;
int begin = left;
int end = right;
// 随机选key
int randi = left + (rand() % (right - left + 1));
Swap(&a[left], &a[randi]);
//也可以三值取中选key
//int key = MedianOfThree(arr, left, right);
int prev = left;
int cur = prev + 1;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
++cur;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
// [begin, keyi-1] keyi [keyi+1, end]
IntroSort(a, begin, keyi - 1, depth, defaultDepth);
IntroSort(a, keyi + 1, end, depth, defaultDepth);
}
void QuickSort(int* a, int left, int right)
{
int depth = 0;
int logn = 0;
int N = right - left + 1;
for (int i = 1; i < N; i *= 2)
{
logn++;
}
// introspective sort -- ⾃省排序
IntroSort(a, left, right, depth, logn * 2);
}
int* sortArray(int* nums, int numsSize, int* returnSize)
{
srand(time(0));
QuickSort(nums, 0, numsSize - 1);
*returnSize = numsSize;
return nums;
}我这里的代码演示是直接在力扣上排序数组这道题里测试的，这个题目也是非常有意思的，官方的快排答案竟然过不了。大家可以用我们上面实现的三路划分或者这个自省排序，都可以通过这道题，当然像其它的几个时间复杂度比较优秀的排序算法也可以通过。
往期回顾：
【数据结构初阶】--排序(五)--计数排序，排序算法复杂度对比和稳定性分析
结语：本篇博客就到此结束了，大家如果是快速排序掌握的还可以的话，可以好好学习一下这篇博客中的一些优化的方法，如果时间不够或者之前掌握的不牢固的可以先放一放，后续再来学习，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。