【数据结构初阶】--快速排序进阶
🔥个人主页：@草莓熊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[mid], &arr[right]);}if (arr[mid] = 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[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#include#include#includevoid 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 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[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 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 = 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[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 defaultDepth){HeapSort(a + left, right - left + 1);return;}depth++;int begin = left;int end = right;// 随机选keyint 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;}我这里的代码演示是直接在力扣上排序数组这道题里测试的，这个题目也是非常有意思的，官方的快排答案竟然过不了。大家可以用我们上面实现的三路划分或者这个自省排序，都可以通过这道题，当然像其它的几个时间复杂度比较优秀的排序算法也可以通过。
题目链接：912. 排序数组 - 力扣（LeetCode）
往期回顾：
【数据结构初阶】--排序(一)：直接插入排序，希尔排序
【数据结构初阶】--排序(二)--直接选择排序，堆排序
【数据结构初阶】--排序(三)：冒泡排序，快速排序
【数据结构初阶】--排序(四)：归并排序
【数据结构初阶】--排序(五)--计数排序，排序算法复杂度对比和稳定性分析
结语：本篇博客就到此结束了，大家如果是快速排序掌握的还可以的话，可以好好学习一下这篇博客中的一些优化的方法，如果时间不够或者之前掌握的不牢固的可以先放一放，后续再来学习，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。
