跳到主要内容
快速排序算法发展历程及三路划分、内省排序实现 | 极客日志
C 算法
快速排序算法发展历程及三路划分、内省排序实现 综述由AI生成 快速排序由托尼·霍尔发明,基于分治策略。针对最坏情况 O(N^2),后续发展出随机化基准、三数取中、小数组插入排序优化、三路划分处理重复数据及内省排序结合堆排序等改进方案。梳理了快速排序的演变历史,详细解析了三路快速排序与内省排序的核心思想,并提供 C 语言完整实现代码,最后通过 LeetCode 题目对比不同分区算法的实际性能表现。
菩提 发布于 2026/3/24 更新于 2026/5/23 17 浏览快速排序的前世今生
前言
在数据结构的学习中,快速排序常被视为排序算法中的王者。看似光鲜的冠军背后,必有一段不寻常的成长历程。快速排序能登上排序算法的巅峰,经历了从理论雏形到工程优化的漫长蜕变。本文将沿着时间的脉络,走进快速排序的'前世今生',探寻其诞生与发展的秘密。
起源
一、诞生
快速排序(Quicksort) :由英国计算机科学家托尼・霍尔(Tony Hoare)在 1960 年发明。当时霍尔年仅 25 岁,受英国国家物理实验室派遣,赴莫斯科国立大学研究机器翻译时,为了解决俄语词序的随机排列问题,灵光一现发明了快速排序。1961 年,他在《计算机学报》(Communications of the ACM)上发表论文《Quicksort》,正式将这一算法引入学术界。快速排序也被称为'20 世纪十大算法'之一,霍尔因其贡献获得 1980 年图灵奖(Turing Award),评委会称其'对算法理论和编程实践产生了深远影响'。因其平均性能优异且空间效率高,快速排序同时也是 C++ 标准库 std::sort、Java 标准库 Arrays.sort 的核心算法。
二、突破
快速排序的关键突破 :
分治策略 :将数组分成两部分,通过选择一个'基准值(pivot)',将小于基准的元素放在左边,大于基准的放在右边,再递归排序左右子数组。
原址排序 :无需额外存储大量中间数据,空间复杂度为 O(log n)(递归栈空间),适合处理大规模数据。
三、核心
快速排序的三大法则 :
基准(Pivot) :随机选中一个元素作为分界线。
分区(Partition) :把数组拆成「小值左子数组」和「大值右子数组」。
递归(recursion) :对左右子数组重复上述操作。
'快速排序就像一位优雅的剑客——看似随意挥剑,实则每一击都将问题一分为二。'
发展
快速排序的性能核心,在于每次单趟排序时基准值(key)对数组的划分效果。若每次选择的基准值都能将数组近乎二等分,其递归树就会形成均匀的满二叉树,此时算法性能最优。若每次选取的基准值都是数组中的最小值或最大值,数组会被划分为 0 个元素和 N-1 个元素的子问题,时间复杂度将退化为 O(N²)。
在实际应用中,有多种数据特性会显著影响快速排序对数组的划分效果,其中 数据有序性 和 重复元素分布 是两个关键因素:
数据完全有序或近乎有序 :当待排序数组呈现升序、降序,或大部分元素已处于有序状态时,若采用默认的固定基准选取策略(如:首元素),会导致每次分区极度不平衡 —— 一侧子数组为空,另一侧包含全部剩余元素。这将使快速排序的时间复杂度从理想的 O(n log n) 退化为 O(n²),性能大幅下降。
数组存在大量重复数据 :当待排序数组中重复元素占比较高时,传统快速排序容易将重复值集中分配到某一个子数组中,造成分区失衡。例如:若基准值恰好为重复元素,可能会使一侧子数组规模远大于另一侧,导致递归树深度增加,同样引发性能恶化。
快速排序的发展历程,本质上就是针对上述问题不断优化迭代的过程。从基准值随机化、三数取中解决数据有序性导致的最坏情况,到三路快速排序、双路快速排序专门应对重复数据场景,每一次改进都在拓展快速排序的适用边界,使其在复杂数据环境下仍能保持高效稳定。
1. 早期版本:简单但不稳定
1960 年:初始版本
提出者 :英国 托尼・霍尔(Tony Hoare)
特点 :最初的快速排序采用固定基准值(如:第一个元素),这导致在最坏情况下(如:数组已排序)时间复杂度退化为 O(n²)。尽管平均时间复杂度为 O(n log n),但实际应用中仍存在性能瓶颈。
2. 基准值优化:打破最坏情况
1970 年代:随机化基准
思想 :随机选择基准值,而非固定位置(如:首元素)。
破局 :将最坏情况(如:有序数组)的概率降至极低,确保实际应用中平均性能稳定,避免因数据分布导致的性能暴跌。
影响 :使快速排序的平均性能更稳定,成为工业界标准实现的核心优化。
1970 年代末:三数取中法
思想 :取数组首、中、尾元素的中位数作为基准,减少极端数据,尤其在数组已经有序的情况下。
破局 :进一步优化有序、逆序或重复数据的分区效果,提升排序稳定性。
影响 :被早期 C 库 qsort 采用,成为工程实践中平衡数据分布的经典方法。
3. 分区优化:减少递归开销
1977 年:三路快速排序
提出者 :荷兰 艾兹格·迪杰斯特拉(Edsger Dijkstra)
思想 :将数组划分为'小于基准'、'等于基准'、'大于基准'三部分,对重复元素直接跳过递归,仅排序小于和大于基准的部分。
破局 :处理大量重复元素(如:{3,3,2,3,4})时,时间复杂度优化为 O(n)(重复元素占比高时),避免无效递归。
影响 :被 Python sorted()、C++ std::stable_sort(部分实现)采用,成为处理重复数据的标准解法。
1980 年代:小数组优化
思想 :当子数组长度小于阈值(如:16)时,切换为插入排序(利用插入排序在小规模数据上的常数因子优势)。
破局 :减少递归开销,提升小规模数据的排序速度,优化实际运行效率。
影响 :成为所有高效排序算法的标配优化(如:归并排序、堆排序也采用类似策略),广泛应用于工业级代码。
1997 年:内省排序
提出者 :美国 大卫・R・穆瑟(David R. Musser)
思想 :结合快速排序、堆排序、插入排序:递归深度超过 O(log n) 时(触发最坏情况预警),切换为堆排序(确保最坏时间复杂度 O(n log n));子数组长度小于阈值时,切换为插入排序。
破局 :彻底解决快速排序的最坏情况问题,确保绝对稳定的 O(n log n) 时间复杂度,适用于所有数据分布。
影响 :成为 C++ std::sort 的标准实现,奠定现代工业级排序算法的基础,被广泛应用于 C++ 标准库。
2009 年:双路快速排序
提出者 :俄罗斯 弗拉基米尔・雅罗斯拉夫斯基(Vladimir Yaroslavskiy)
思想 :使用两个基准值(通常取首、尾元素),将数组划分为三部分:<pivot1、[pivot1, pivot2]、>pivot2,减少递归深度。
破局 :在均匀分布数据中,分区更平衡,递归次数更少,提升平均性能,尤其适用于基本数据类型排序。
影响 :被 Java 7 Arrays.sort(基本类型排序)采用,成为 JVM 排序的核心优化,提升 Java 语言的排序性能。
实现
一、实现:三路快速排序
什么是三路快速排序? 三路快速排序(3-Way QuickSort) :是快速排序的高效变种,专门用于处理含有大量重复元素的数组。它通过将数组划分为三个部分(小于、等于和大于基准值的元素)来优化性能,相比传统快速排序能显著减少重复元素的重复比较和交换操作。
三路快速排序的核心思想是什么?
选择基准值 :取区间最左元素作为基准值,即:key = a[left]
初始化指针 :
lt = left:指向小于基准值区间的右边界(初始为基准值位置)
gt = right:指向大于基准值区间的左边界(初始为区间末尾)
cur = left + 1:当前遍历指针,从基准值右侧开始扫描
遍历与交换(当 cur <= gt 时循环) :
若 a[cur] < key:将 a[cur] 与 a[lt] 交换,使该元素进入小于区。lt++(小于区右边界右移),cur++(继续扫描下一个元素)。
若 a[cur] > key:将 a[cur] 与 a[gt] 交换,使该元素进入大于区。gt--(大于区左边界左移),cur 不移动(交换后的 a[cur] 需重新判断与 key 的大小关系)。
若 a[cur] == key:直接跳过,cur++(该元素留在等于区)。
递归排序 :
对小于区(left 至 lt - 1)递归调用三路快排。
对大于区(gt + 1 至 right)递归调用三路快排。
对等于区(lt 至 gt)无需处理,已自然有序。
怎么实现三路快速排序? 下面的程序文件中,不仅包含我们接下来要实现的'三路快速排序',还涵盖了之前已实现的其他三个快速排序版本,所以说下面的文件中将会展示快速排序的四种实现版本:Hoare 版、Lomuto 版、挖坑版、三路划分版。
头文件:QuickSort3Way.h #pragma once
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
typedef struct {
int leftKeyIdx;
int rightKeyIdx;
} KeyWayIdx;
void Swap (int * a, int * b) ;
void PrintArray (int * a, int n) ;
int PartSort1 (int * a, int left, int right) ;
int PartSort2 (int * a, int left, int right) ;
int PartSort3 (int * a, int left, int right) ;
KeyWayIdx QuickSort3Way (int * a, int left, int right) ;
void QuickSort (int * a, int left, int right) ;
实现文件:QuickSort3Way.c #include "QuickSort3Way.h"
void Swap (int * a, int * b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void PrintArray (int * a, int n) {
for (int i = 0 ; i < n; i++) {
printf ("%d " , a[i]);
}
printf ("\n" );
}
int PartSort1 (int * a, int left, int right) {
int key = left;
while (left < right) {
while (left < right && a[right] >= a[key]) {
right--;
}
while (left < right && a[left] <= a[key]) {
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[key], &a[left]);
return left;
}
int PartSort2 (int * a, int left, int right) {
int key = left;
int slow = left;
int fast = left + 1 ;
while (fast <= right) {
if (a[fast] < a[key]) {
if (a[fast] != a[slow])
{
slow++;
Swap(&a[fast], &a[slow]);
}
}
fast++;
}
Swap(&a[key], &a[slow]);
return slow;
}
int PartSort3 (int * a, int left, int right) {
int mid = left + (rand() % (right - left));
Swap(&a[left], &a[mid]);
int key = a[left];
int hole = left;
int begin = left, end = right;
while (begin < end) {
while (begin < end && a[end] >= key) {
end--;
}
a[hole] = a[end];
hole = end;
while (begin < end && a[begin] <= key) {
begin++;
}
a[hole] = a[begin];
hole = begin;
}
a[hole] = key;
return hole;
}
KeyWayIdx QuickSort3Way (int * a, int left, int right) {
int key = a[left];
int curr = left + 1 ;
while (curr <= right) {
if (a[curr] < key) {
}
else if (a[curr] > key) {
}
curr++;
}
KeyWayIdx kwi;
kwi.leftKeyIdx = left;
kwi.rightKeyIdx = right;
return kwi;
}
void QuickSort (int * a, int left, int right) {
if (left >= right)
return ;
测试文件:Test.c #include "QuickSort3Way.h"
bool isSorted (int * arr, int size) {
for (int i = 0 ; i < size - 1 ; i++) {
if (arr[i] > arr[i + 1 ]) {
return false ;
}
}
return true ;
}
void generateRandomArray (int * arr, int size, int range) {
srand((unsigned int )time(NULL ));
for (int i = 0 ; i < size; i++) {
arr[i] = rand() % range;
}
}
void testDuplicateElements () {
printf ("===== 测试重复元素数组 =====\n" );
int arr[] = {3 , 1 , 4 , 1 , 5 , 9 , 2 , 6 , 5 , 3 , 5 };
int size = sizeof (arr) / sizeof (arr[0 ]);
printf ("排序前:" );
PrintArray(arr, size);
QuickSort(arr, 0 , size - 1 );
printf ("排序后:" );
PrintArray(arr, size);
if (isSorted(arr, size))
printf ("测试通过:重复元素数组已正确排序\n" );
else
printf ("测试失败:重复元素未正确处理\n" );
printf ("\n" );
}
void testAllIdentical () {
printf ("===== 测试全相同数组 =====\n" );
int arr[] = {7 , 7 , 7 , 7 , 7 , 7 };
int size = sizeof (arr) / sizeof (arr[0 ]);
printf ("排序前:" );
PrintArray(arr, size);
QuickSort(arr, 0 , size - 1 );
printf ("排序后:" );
PrintArray(arr, size);
if (isSorted(arr, size))
printf ("测试通过:全相同数组保持有序\n" );
else
printf ("测试失败:全相同数组异常\n" );
printf ("\n" );
}
void testAlreadySorted () {
printf ("===== 测试已排序数组 =====\n" );
int arr[] = {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 };
int size = sizeof (arr) / sizeof (arr[0 ]);
printf ("排序前:" );
PrintArray(arr, size);
QuickSort(arr, 0 , size - 1 );
printf ("排序后:" );
PrintArray(arr, size);
if (isSorted(arr, size)) {
printf ("测试通过:已排序数组保持有序\n" );
} else {
printf ("测试失败:已排序数组被破坏\n" );
}
printf ("\n" );
}
void testReverseSorted () {
printf ("===== 测试逆序数组 =====\n" );
int arr[] = {9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 };
int size = sizeof (arr) / sizeof (arr[0 ]);
printf ("排序前:" );
PrintArray(arr, size);
QuickSort(arr, 0 , size - 1 );
printf ("排序后:" );
PrintArray(arr, size);
if (isSorted(arr, size))
printf ("测试通过:逆序数组已正确排序\n" );
else
printf ("测试失败:逆序数组未正确排序\n" );
printf ("\n" );
}
void testLargeArrayPerformance () {
printf ("===== 大数组性能测试 =====\n" );
const int size = 100000 ;
int * arr = (int *)malloc (size * sizeof (int ));
generateRandomArray(arr, size, size / 10 );
clock_t start = clock();
QuickSort(arr, 0 , size - 1 );
clock_t end = clock();
double elapsed = (double )(end - start) / CLOCKS_PER_SEC;
printf ("排序%d个元素耗时:%.3f 秒\n" , size, elapsed);
if (isSorted(arr, size))
printf ("排序结果正确\n" );
else
printf ("排序结果错误\n" );
free (arr);
printf ("\n" );
}
int main () {
testDuplicateElements();
testAllIdentical();
testAlreadySorted();
testReverseSorted();
testLargeArrayPerformance();
printf ("====== 三路快速排序测试完成 ======\n" );
return 0 ;
}
二、实现:内省排序
什么是内省排序? 内省排序(Introsort,也称内省式排序 introspective sort) :是一种结合了快速排序、堆排序和插入排序优势的混合排序算法。主要用于解决快速排序在最坏情况下时间复杂度退化到 O(n²) 的问题,同时保持快速排序在平均情况下的高效性。它结合了快速排序、堆排序和插入排序的优点,通过动态切换排序策略来确保在各种情况下都能达到 O(n log n) 的时间复杂度。
内省排序的核心思想是什么? 内省排序的核心思想 :通过监测递归深度来避免快速排序的最坏情况,具体策略如下:
快速排序为主 :首先使用快速排序进行排序,利用其平均情况下的高效性 O(n log n)。
堆排序切换 :当递归深度超过一定阈值(通常为 2 log n,n 为待排序元素数量)时,说明数据可能退化为最坏情况(如:完全有序数组),此时切换为堆排序。堆排序的时间复杂度始终为 O(n log n),虽然常数因子较大,但能保证最坏情况下的性能。
插入排序优化 :当待排序序列长度较小时(如:小于某个阈值,通常为 16),切换为插入排序,利用其在小规模数据下的高效性。
确定递归深度阈值 :阈值通常设为 2 × log₂n(n 为数组长度),用于判断是否切换为堆排序。
快速排序递归 :选择基准值(如:三数取中法),将数组划分为左右两部分。对左右子数组递归调用内省排序,同时记录当前递归深度。若递归深度超过阈值,停止快速排序,转为堆排序。
堆排序处理 :对当前子数组构建最大堆,然后通过堆排序完成排序,确保最坏情况下时间复杂度为 O(n log n)。
插入排序优化 :当子数组长度小于阈值(如:16)时,直接使用插入排序,减少递归开销。
怎么实现内省排序
头文件:IntroSort.h #pragma once
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
void Swap (int * a, int * b) ;
void PrintArray (int * a, int n) ;
void AdjustDown (int * a, int parent, int n) ;
void QuickSort (int * a, int left, int right) ;
void InsertSort (int * a, int n) ;
void HeapSort (int * a, int n) ;
实现文件:IntroSort.c #include "IntroSort.h"
void Swap (int * a, int * b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void PrintArray (int * a, int n) {
for (int i = 0 ; i < n; i++) {
printf ("%d " , a[i]);
}
printf ("\n" );
}
void AdjustDown (int * a, int parent, int n) {
int maxChild = (parent << 1 ) + 1 ;
while (maxChild < n)
{
if (maxChild + 1 < n && a[maxChild + 1 ] > a[maxChild]) {
maxChild = maxChild + 1 ;
}
if (a[parent] >= a[maxChild])
return ;
else {
Swap(&a[parent], &a[maxChild]);
parent = maxChild;
maxChild = (parent << 1 ) + 1 ;
}
}
}
void InsertSort (int * a, int n) {
for (int i = 0 ; i <= n - 2 ; i++)
{
int end = i;
int tmp = a[end + 1 ];
while (end >= 0 ) {
if (a[end] > tmp) {
a[end + 1 ] = a[end];
end--;
} else {
break ;
}
}
a[end + 1 ] = tmp;
}
}
void HeapSort (int * a, int n) {
for (int i = (n - 1 - 1 ) >> 1 ; i >= 0 ; i--) {
AdjustDown(a, i, n);
}
int end = n - 1 ;
while (end > 0 ) {
Swap(&a[0 ], &a[end]);
end--;
AdjustDown(a, 0 , end + 1 );
}
}
void IntroSort (int * a, int left, int right, int depth, int defaultDepth) {
if (left >= right)
return ;
if (right - left + 1 < 16 ) {
InsertSort(a + left, right - left + 1 );
return ;
}
if (depth > defaultDepth) {
HeapSort(a + left, right - left + 1 );
return ;
}
depth++;
int randKey = left + (rand() % (right - left));
Swap(&a[randKey], &a[left]);
int key = left;
int slow = left;
int fast = slow + 1 ;
while (fast <= right) {
if (a[fast] < a[key] && ++slow != fast) {
Swap(&a[fast], &a[slow]);
}
fast++;
}
Swap(&a[key], &a[slow]);
key = slow;
IntroSort(a, left, key - 1 , depth, defaultDepth);
IntroSort(a, key + 1 , right, depth, defaultDepth);
}
void QuickSort (int * a, int left, int right) {
int depth = 0 ;
int logn = 0 ;
for (int i = 1 ; i < right - left + 1 ; i *= 2 )
{
logn++;
}
IntroSort(a, left, right, depth, logn * 2 );
}
测试文件:Test.c #include "IntroSort.h"
bool isSorted (int * arr, int size) {
for (int i = 0 ; i < size - 1 ; i++) {
if (arr[i] > arr[i + 1 ]) {
return false ;
}
}
return true ;
}
void testRandomArray () {
printf ("===== 测试随机数组 =====\n" );
int arr[] = {3 , 1 , 4 , 1 , 5 , 9 , 2 , 6 , 5 , 3 };
int size = sizeof (arr) / sizeof (arr[0 ]);
printf ("排序前:" );
PrintArray(arr, size);
QuickSort(arr, 0 , size - 1 );
printf ("排序后:" );
PrintArray(arr, size);
if (isSorted(arr, size))
printf ("测试通过:数组已正确排序\n" );
else
printf ("测试失败:数组未正确排序\n" );
printf ("\n" );
}
void testSortedArray () {
printf ("===== 测试已排序数组 =====\n" );
int arr[] = {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 };
int size = sizeof (arr) / sizeof (arr[0 ]);
printf ("排序前:" );
PrintArray(arr, size);
QuickSort(arr, 0 , size - 1 );
printf ("排序后:" );
PrintArray(arr, size);
if (isSorted(arr, size))
printf ("测试通过:数组保持有序\n" );
else
printf ("测试失败:数组顺序被破坏\n" );
printf ("\n" );
}
void testReverseSortedArray () {
printf ("===== 测试逆序数组 =====\n" );
int arr[] = {9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 };
int size = sizeof (arr) / sizeof (arr[0 ]);
printf ("排序前:" );
PrintArray(arr, size);
QuickSort(arr, 0 , size - 1 );
printf ("排序后:" );
PrintArray(arr, size);
if (isSorted(arr, size))
printf ("测试通过:数组已正确排序\n" );
else
printf ("测试失败:数组未正确排序\n" );
printf ("\n" );
}
void testUniformArray () {
printf ("===== 测试全相同数组 =====\n" );
int arr[] = {5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 };
int size = sizeof (arr) / sizeof (arr[0 ]);
printf ("排序前:" );
PrintArray(arr, size);
QuickSort(arr, 0 , size - 1 );
printf ("排序后:" );
PrintArray(arr, size);
if (isSorted(arr, size))
printf ("测试通过:数组保持有序\n" );
else
printf ("测试失败:数组顺序被破坏\n" );
printf ("\n" );
}
void testSmallArray () {
printf ("===== 测试小数组 =====\n" );
int arr[] = {7 , 3 };
int size = sizeof (arr) / sizeof (arr[0 ]);
printf ("排序前:" );
PrintArray(arr, size);
QuickSort(arr, 0 , size - 1 );
printf ("排序后:" );
PrintArray(arr, size);
if (isSorted(arr, size))
printf ("测试通过:小数组已正确排序\n" );
else
printf ("测试失败:小数组未正确排序\n" );
printf ("\n" );
}
void testLargeArray () {
printf ("===== 测试大数组性能 =====\n" );
const int size = 100000 ;
int * arr = (int *)malloc (size * sizeof (int ));
if (arr == NULL ) {
perror("malloc fail" );
return ;
}
srand((unsigned int )time(NULL ));
for (int i = 0 ; i < size; i++) {
arr[i] = rand() % size;
}
printf ("开始排序%d个元素...\n" , size);
clock_t start = clock();
QuickSort(arr, 0 , size - 1 );
clock_t end = clock();
double time_spent = (double )(end - start) / CLOCKS_PER_SEC;
if (isSorted(arr, size)) {
printf ("测试通过:大数组已正确排序\n" );
printf ("排序耗时:%.3f 秒\n" , time_spent);
} else {
printf ("测试失败:大数组未正确排序\n" );
}
free (arr);
printf ("\n" );
}
int main () {
testRandomArray();
testSortedArray();
testReverseSortedArray();
testUniformArray();
testSmallArray();
testLargeArray();
printf ("===== 所有测试完成 =====\n" );
return 0 ;
}
实践
LeetCode 912. 排序数组
题目介绍
方法一:Hoare 版——快速排序
void Swap (int * a, int * b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
int PartSort1 (int * a, int left, int right) {
int mid = left + (rand() % (right - left));
Swap(&a[left], &a[mid]);
int key = left;
while (left < right) {
while (left < right && a[right] >= a[key]) {
right--;
}
while (left < right && a[left] <= a[key]) {
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[key], &a[left]);
return left;
}
void QuickSort (int * a, int left, int right) {
if (left >= right)
return ;
int key = PartSort1(a, left, right);
QuickSort(a, left, key - 1 );
QuickSort(a, key + 1 , right);
}
int * sortArray (int * nums, int numsSize, int * returnSize) {
QuickSort(nums, 0 , numsSize - 1 );
*returnSize = numsSize;
return nums;
}
方法二:Lomuto 版——快速排序
void Swap (int * a, int * b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
int PartSort2 (int * a, int left, int right) {
int mid = left + (rand() % (right - left));
Swap(&a[left], &a[mid]);
int key = left;
int slow = left;
int fast = left + 1 ;
while (fast <= right) {
if (a[fast] < a[key] && ++slow != fast) {
Swap(&a[slow], &a[fast]);
}
fast++;
}
Swap(&a[key], &a[slow]);
return slow;
}
void QuickSort (int * a, int left, int right) {
if (left >= right)
return ;
int key = PartSort2(a, left, right);
QuickSort(a, left, key - 1 );
QuickSort(a, key + 1 , right);
}
int * sortArray (int * nums, int numsSize, int * returnSize) {
QuickSort(nums, 0 , numsSize - 1 );
*returnSize = numsSize;
return nums;
}
方法三:挖坑版——快速排序
void Swap (int * a, int * b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
int PartSort3 (int * a, int left, int right) {
int mid = left + (rand() % (right - left));
Swap(&a[left], &a[mid]);
int key = a[left];
int hole = left;
int begin = left, end = right;
while (begin < end) {
while (begin < end && a[end] >= key) {
end--;
}
a[hole] = a[end];
hole = end;
while (begin < end && a[begin] <= key) {
begin++;
}
a[hole] = a[begin];
hole = begin;
}
a[hole] = key;
return hole;
}
void QuickSort (int * a, int left, int right) {
if (left >= right)
return ;
int key = PartSort3(a, left, right);
QuickSort(a, left, key - 1 );
QuickSort(a, key + 1 , right);
}
int * sortArray (int * nums, int numsSize, int * returnSize) {
QuickSort(nums, 0 , numsSize - 1 );
*returnSize = numsSize;
return nums;
}
方法四:三路划分版——快速排序
typedef struct {
int leftKeyIdx;
int rightKeyIdx;
} KeyWayIdx;
void Swap (int * a, int * b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
KeyWayIdx QuickSort3Way (int * a, int left, int right) {
int mid = left + (rand() % (right - left));
Swap(&a[left], &a[mid]);
int key = a[left];
int curr = left + 1 ;
while (curr <= right) {
if (a[curr] < key) {
}
else if (a[curr] > key) {
}
curr++;
}
KeyWayIdx kwi;
kwi.leftKeyIdx = left;
kwi.rightKeyIdx = right;
return kwi;
}
void QuickSort (int * a, int left, int right) {
if (left >= right)
return ;
KeyWayIdx kwi = QuickSort3Way(a, left, right);
QuickSort(a, left, kwi.leftKeyIdx - 1 );
QuickSort(a, kwi.rightKeyIdx + 1 , right);
}
int * sortArray (int * nums, int numsSize, int * returnSize) {
QuickSort(nums, 0 , numsSize - 1 );
*returnSize = numsSize;
return nums;
}
方法五:内省排序——快排进阶
void Swap (int * a, int * b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void PrintArray (int * a, int n) {
for (int i = 0 ; i < n; i++) {
printf ("%d " , a[i]);
}
printf ("\n" );
}
void AdjustDown (int * a, int parent, int n) {
int maxChild = (parent << 1 ) + 1 ;
while (maxChild < n) {
if (maxChild + 1 < n && a[maxChild + 1 ] > a[maxChild]) {
maxChild = maxChild + 1 ;
}
if (a[parent] >= a[maxChild])
return ;
else {
Swap(&a[parent], &a[maxChild]);
parent = maxChild;
maxChild = (parent << 1 ) + 1 ;
}
}
}
void InsertSort (int * a, int n) {
for (int i = 0 ; i <= n - 2 ; i++) {
int end = i;
int tmp = a[end + 1 ];
while (end >= 0 ) {
if (a[end] > tmp) {
a[end + 1 ] = a[end];
end--;
} else {
break ;
}
}
a[end + 1 ] = tmp;
}
}
void HeapSort (int * a, int n) {
for (int i = (n - 1 - 1 ) >> 1 ; i >= 0 ; i--) {
AdjustDown(a, i, n);
}
int end = n - 1 ;
while (end > 0 ) {
Swap(&a[0 ], &a[end]);
end--;
AdjustDown(a, 0 , end + 1 );
}
}
void IntroSort (int * a, int left, int right, int depth, int defaultDepth) {
if (left >= right)
return ;
if (right - left + 1 < 16 ) {
InsertSort(a + left, right - left + 1 );
return ;
}
if (depth > defaultDepth) {
HeapSort(a + left, right - left + 1 );
return ;
}
depth++;
int randKey = left + (rand() % (right - left));
Swap(&a[randKey], &a[left]);
int key = left;
int slow = left;
int fast = slow + 1 ;
while (fast <= right) {
if (a[fast] < a[key] && ++slow != fast) {
Swap(&a[fast], &a[slow]);
}
fast++;
}
Swap(&a[key], &a[slow]);
key = slow;
IntroSort(a, left, key - 1 , depth, defaultDepth);
IntroSort(a, key + 1 , right, depth, defaultDepth);
}
void QuickSort (int * a, int left, int right) {
int depth = 0 ;
int logn = 0 ;
for (int i = 1 ; i < right - left + 1 ; i *= 2 ) {
logn++;
}
IntroSort(a, left, right, depth, logn * 2 );
}
int * sortArray (int * nums, int numsSize, int * returnSize) {
QuickSort(nums, 0 , numsSize - 1 );
*returnSize = numsSize;
return nums;
}
结果分析 演示的前三个分区算法都进行了'随机化基准'的优化,因为如果不这样做的话,没等遇到含有特殊数据的数组——大量重复数据的数组,在面对含有大量数据的数组的时候就超时了。
OJ 分析 :通过上面这道 OJ 的练习,我们可以总结出下面的一些信息:
时间复杂度为 O(N²) 的排序算法无法通过,并且当使用快排时,传统的 Hoare 和 Lomuto 方法也无法通过该题目。这是因为:该题的测试用例中,不仅有数据量庞大的大数组,还有一些特殊数据的数组,比如:含有大量重复数据的数组。
而希尔排序、堆排序、归并排序则可以通过。这是因为:堆排序、归并排序和希尔排序受数据样本的分布和形态影响较小。但快排不同,由于快排需要选择基准值(key),如果每次基准值的选择都使得当趟分割结果很不均衡,就会出现效率退化的问题。
结语 从实验室中的理论构想,到工业界的标配工具,快速排序历经六十余年仍焕发活力。
它不仅是排序问题的高效解法,更蕴含着分治、优化、随机化等算法设计思想,持续启发着计算机科学的发展。
正如霍尔本人所说:'算法的价值不仅在于解决问题,更在于教会我们如何思考问题。'
相关免费在线工具 加密/解密文本 使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
Gemini 图片去水印 基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
Markdown转HTML 将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online