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