快速排序是面试和笔试里出现频率最高的排序算法之一常考常新。很多人能背出“选基准、分左右、递归排序”这几句话但真到写代码或者分析时间复杂度时却容易栽在分区边界、递归终止和退化情况上。这次我们换一种思路用“动画演示 逐帧拆解”的方式把快速排序从原理到代码完整过一遍重点对比 C 语言和 Java 实现的差异并给出可以直接运行的源码。快速排序的核心优势很明确平均时间复杂度 O(n log n)常数系数小内排序场景下综合表现优秀是绝大多数语言标准库排序实现的基础思路。但它不是没有短板最坏情况时间复杂度退化到 O(n²)而且递归深度在大数据量时可能触发栈溢出。理解这些问题才算真正掌握快速排序而不只是记住模板代码。本文会按照“算法思想 - 动画逐轮拆解 - C 语言实现 - Java 实现 - Python 实现 - 优化方案 - 复杂度分析 - 常见错误排查”的顺序展开。无论你是准备校招笔试还是在项目中需要手写排序逻辑这篇文章都值得收藏备用。1. 核心特性速览在开始写代码之前先用一张表把快速排序的关键特性梳理清楚。特性项说明算法类别比较类排序 / 内部排序平均时间复杂度O(n log n)最坏时间复杂度O(n²)平均空间复杂度O(log n)主要由递归调用栈产生最坏空间复杂度O(n)递归深度达到 n 时出现稳定性不稳定排序方式原地排序in-place无需额外大型数组核心思想分治法Divide and Conquer分区策略常见有 Hoare 分区和 Lomuto 分区两种典型应用大数据量排序、标准库排序底层、TopK 问题、第 K 大元素查找快速排序的“快”主要体现在平均情况下。它不像归并排序需要额外 O(n) 的辅助数组也不像堆排序虽然最坏情况稳定但常数较大。快速排序在绝大多数随机数据上表现都非常好这也是它为什么在很多语言的标准库中占据核心位置。需要特别强调一点快速排序不稳定。如果待排序数据中有值相等但需要保持原始顺序的元素快速排序不一定能保住这个相对顺序。这是它在某些业务场景比如数据库排序需要多字段稳定排序中不如归并排序的地方。2. 动画讲解快速排序的执行过程没有动画的排序讲解是不完整的。这里把快速排序拆成几个阶段每一轮都当作一帧动画来分析。理解这些“帧”后续写代码就有了清晰的方向。2.1 整体流程预览快速排序的完整过程可以概括为三个阶段选取基准 - 分区操作 - 递归排序。这三个阶段循环套用直到数组完全有序。第一阶段是“选取基准”。基准pivot可以是数组的第一个元素、最后一个元素、中间元素也可以随机选取。基准选择直接关系到排序的性能后面会在优化章节详细展开。第二阶段是“分区操作”。这是快速排序的灵魂。分区要做的事情是把数组重新排列一遍保证基准元素最终落在排序后的正确位置上并且基准左边的所有元素不大于基准右边所有元素不小于基准。第三阶段是“递归排序”。基准把数组分成左右两半之后左边子数组和右边子数组依然是无序的需要分别递归执行快速排序。递归的出口是子数组长度为 0 或 1此时数组天然有序。2.2 第一轮动画初始分区假设待排序数组为[49, 38, 65, 97, 76, 13, 27, 49]为了便于观察选择第一个元素 49 作为基准元素。基准可以理解为把整个数组分成两边的“标杆”。动画第一帧所有元素处于原始无序状态基准 49 被单独标记出来。动画第二帧分区过程开始扫描数组。这里的核心思路是从右向左找小于等于 49 的元素从左向右找大于等于 49 的元素找到后就交换这两个元素的位置。比如右侧扫描发现 27 小于 49左侧扫描发现 65 大于 49交换 27 和 65。这一步让小于基准的值不断靠近左边大于基准的值不断靠近右边。动画第三帧继续扫描右侧发现 13 小于 49左侧发现 97 大于 49交换 13 和 97。此时数组变成[49, 38, 27, 13, 76, 97, 65, 49]动画第四帧左右扫描指针相遇分区结束。把基准 49 和当前指针位置的元素交换。这里需要注意Hoare 分区和 Lomuto 分区在指针相遇位置的处理上有所不同动画演示的是 Hoare 分区的效果。第一轮动画结束后数组变成[27, 38, 13, 49, 76, 97, 65, 49]此时第一个 49 已经处于最终排序位置。它的左边是[27, 38, 13]右边是[76, 97, 65, 49]。观察一下左边全部小于 49右边全部大于等于 49。2.3 第二轮动画左右子数组递归接下来对基准左边的[27, 38, 13]单独执行快速排序右边[76, 97, 65, 49]同时单独执行。先看左子数组[27, 38, 13]。选择 27 作为基准。动画演示中可以看到13 和 38 被扫描最终 27 和 13 交换左子数组变为[13, 27, 38]此时 27 已经到达正确位置左侧只剩[13]右侧只剩[38]这两个子数组长度为 1不需要再排序。左半部分完成。右子数组[76, 97, 65, 49]选择 76 作为基准。动画演示中能看到 49 被交换到前面数组变为[49, 65, 76, 97]76 到达正确位置。左侧[49, 65]继续递归选择 49 作为基准此时 65 大于 49交换位置得到[49, 65]右侧[97]无需排序。至此整个数组排序完成[13, 27, 38, 49, 49, 65, 76, 97]2.4 动画中必须记住的三个关键现象第一个关键现象每一轮分区结束后基准元素就已经固定在最正确的位置后面不会再移动。观察上面的过程第一轮的 49、第二轮的 27 和 76、第三轮的 13 和 97每个都是分区后立即“归位”。总元素数为 n那么每轮归位一个元素最多需要 n 轮这就是快速排序最坏情况时间复杂度的直观来源。第二个关键现象真正决定子数组是否继续递归的关键是“长度”。一旦子数组长度为 0 或 1递归立即停止。很多代码实现错误地写成left right而不是left pivotIndex这类条件最终导致无限递归或栈溢出。第三个关键现象两个值相等的 49 在最终结果中依然存在但它们的相对顺序可能发生改变。原始数组中有两个 49排序后依然有两个 49但谁在前谁在后取决于分区策略。这就是快速排序“不稳定”的直观原因。3. 快速排序 C 语言实现下面给出可以直接编译运行的 C 语言快速排序完整代码。代码采用经典 Hoare 分区方式这也是《算法导论》之外很多教材使用的版本效率高于 Lomuto 分区。#include stdio.h // 交换两个整数的值 void swap(int *a, int *b) { int temp *a; *a *b; *b temp; } // Hoare 分区返回基准元素最终位置 int partition(int arr[], int low, int high) { int pivot arr[low]; // 取第一个元素作为基准 int i low - 1; int j high 1; while (1) { // 从左向右找大于等于 pivot 的元素 do { i; } while (arr[i] pivot); // 从右向左找小于等于 pivot 的元素 do { j--; } while (arr[j] pivot); if (i j) { return j; } swap(arr[i], arr[j]); } } // 快速排序递归函数 void quickSort(int arr[], int low, int high) { if (low high) { int pi partition(arr, low, high); // 基准左侧和右侧分别递归排序 quickSort(arr, low, pi); quickSort(arr, pi 1, high); } } // 打印数组 void printArray(int arr[], int size) { for (int i 0; i size; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {49, 38, 65, 97, 76, 13, 27, 49}; int n sizeof(arr) / sizeof(arr[0]); printf(原始数组: \n); printArray(arr, n); quickSort(arr, 0, n - 1); printf(排序后数组: \n); printArray(arr, n); return 0; }这段代码有几个关键实现细节需要说明。第一点是分区函数中i和j的初始值。i low - 1j high 1配合do...while循环结构保证进入while(1)循环体后i和j会先自增自减再访问元素。这种写法避免了普通while循环可能需要处理边界判断的麻烦但初学者需要一定时间适应。第二点是递归边界。quickSort(arr, low, pi)和quickSort(arr, pi 1, high)。这里使用pi而不是pi - 1是因为 Hoare 分区返回的j可能是一个小于基准原始位置的索引基准元素并不一定恰好位于j位置它可能位于j右侧。这与 Lomuto 分区不同后者的partition返回的pi处一定是基准元素因此递归边界是quickSort(arr, low, pi - 1)和quickSort(arr, pi 1, high)。第三点是编译运行方式。保存为quick_sort.c后在命令行执行gcc quick_sort.c -o quick_sort ./quick_sort输出结果中可以看到原始数组[49 38 65 97 76 13 27 49]会被排序为[13 27 38 49 49 65 76 97]。如果希望使用 Lomuto 分区方式C 语言实现可以替换为下面这个版本#include stdio.h void swap(int *a, int *b) { int temp *a; *a *b; *b temp; } // Lomuto 分区逻辑更直观适合教学 int partitionLomuto(int arr[], int low, int high) { int pivot arr[high]; // 取最后一个元素作为基准 int i low - 1; // i 指向最后一个小于 pivot 的元素 for (int j low; j high; j) { if (arr[j] pivot) { i; swap(arr[i], arr[j]); } } // 基准元素放到正确位置 swap(arr[i 1], arr[high]); return i 1; } void quickSortLomuto(int arr[], int low, int high) { if (low high) { int pi partitionLomuto(arr, low, high); quickSortLomuto(arr, low, pi - 1); quickSortLomuto(arr, pi 1, high); } }Lomuto 分区理解起来更简单遍历数组把所有小于基准的元素交换到数组前部最后把基准放到“小于区”的后面。但缺点也很明显当数组中存在大量重复元素时Lomuto 分区会把数组分成严重不对称的两半导致复杂度接近 O(n²)。Hoare 分区在重复元素较多时表现更好这也是工程实践中更常用 Hoare 分区的原因。4. 快速排序 Java 实现Java 实现的逻辑结构与 C 语言完全一致只是语法层面有差异。这里给出一个完整的 Java 版本可以直接作为QuickSort.java保存并运行。import java.util.Arrays; public class QuickSort { // 交换数组中两个位置的值 private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } // Hoare 分区 private static int partition(int[] arr, int low, int high) { int pivot arr[low]; int i low - 1; int j high 1; while (true) { do { i; } while (arr[i] pivot); do { j--; } while (arr[j] pivot); if (i j) { return j; } swap(arr, i, j); } } public static void quickSort(int[] arr, int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi); quickSort(arr, pi 1, high); } } public static void main(String[] args) { int[] arr {49, 38, 65, 97, 76, 13, 27, 49}; System.out.println(原始数组: Arrays.toString(arr)); quickSort(arr, 0, arr.length - 1); System.out.println(排序后数组: Arrays.toString(arr)); } }运行方式javac QuickSort.java java QuickSort输出结果原始数组: [49, 38, 65, 97, 76, 13, 27, 49] 排序后数组: [13, 27, 38, 49, 49, 65, 76, 97]Java 版本还有一个需要注意的地方Arrays.sort()方法底层对基本类型数组采用 Dual-Pivot QuickSort对引用类型数组采用 TimSort。这里手写快速排序主要为了学习原理而在实际 Java 开发中直接调用Arrays.sort()或者Collections.sort()往往更可靠尤其是在大数据量场景下。4.1 Java 快速排序的传参问题与 C 语言的指针不同Java 中数组等引用类型作为参数传递时传入的是对象引用。因此在quickSort方法内部对数组元素进行交换会直接反映到原始数组上不需要返回值。这一点初学者经常感到困惑但仔细观察代码可以发现swap方法可以直接操作传入的arr数组排序完成后main方法中的arr就已经被修改为目标状态。如果传入的是ArrayListInteger这类集合对象处理方法略有不同但核心逻辑不变。5. 快速排序 Python 实现Python 版本的快速排序有两条路线一种是写成“教学版”代码很优雅、很好理解但会创建新数组空间复杂度不是 O(log n)另一种是仿照 C 语言写“原地版”写法稍复杂但性能表现接近 C/Java。先看教学版写法分为“分区后递归返回新列表”的形式def quicksort_simple(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] left [x for x in arr if x pivot] middle [x for x in arr if x pivot] right [x for x in arr if x pivot] return quicksort_simple(left) middle quicksort_simple(right) arr [49, 38, 65, 97, 76, 13, 27, 49] print(排序前:, arr) sorted_arr quicksort_simple(arr) print(排序后:, sorted_arr)这段代码特别好理解但每次递归都会创建新的列表内存开销很高。更接近工程实践的原地排序版本如下def partition(nums, low, high): pivot nums[low] i low - 1 j high 1 while True: i 1 while nums[i] pivot: i 1 j - 1 while nums[j] pivot: j - 1 if i j: return j nums[i], nums[j] nums[j], nums[i] def quick_sort(nums, low, high): if low high: pi partition(nums, low, high) quick_sort(nums, low, pi) quick_sort(nums, pi 1, high) arr [49, 38, 65, 97, 76, 13, 27, 49] print(排序前:, arr) quick_sort(arr, 0, len(arr) - 1) print(排序后:, arr)Python 原版快速排序的性能瓶颈不在算法本身而在 Python 解释器执行循环的开销。对于 Python 实际项目排序应该使用内置的sorted()方法它是 C 语言级别的 TimSort 实现性能远超手写的 Python 循环版本。Python 版更多用于算法理解、面试演示和复杂度对比。三个语言的实现都放在这里是为了让大家看出算法本质相同只是表达方式有差异。6. 快速排序的优化策略与工程实践上面的代码可以完成排序但还不是最优秀的实现。当数据规模变大或者数据分布极端时需要引入优化手段。6.1 随机化基准当数组接近有序时固定取第一个元素或最后一个元素作为基准会触发最坏情况。比如[1, 2, 3, 4, 5, 6, 7, 8]已经升序排好取第一个元素 1 作为基准分区结果是左边为空、右边为剩余的全部元素每次分区只减少一个元素递归深度达到 n最终时间复杂度退化到 O(n²)。解决办法是随机选择基准。最简单的实现方式在分区之前将arr[low]和随机索引位置的元素交换这样每次基准都是随机的#include stdlib.h #include time.h // 在 C 语言 quickSort 中调用前先随机交换 void quickSortRandom(int arr[], int low, int high) { if (low high) { // 随机选择基准并交换到 low 位置 srand(time(NULL)); int randomIndex low rand() % (high - low 1); swap(arr[randomIndex], arr[low]); int pi partition(arr, low, high); quickSortRandom(arr, low, pi); quickSortRandom(arr, pi 1, high); } }随机化之后最坏情况理论上依然存在但实际触发的概率极低可以认为接近不可能。6.2 三数取中比纯随机更稳定的一种方式取low、mid、high三个位置的元素选择它们的中位数作为基准。这样即使数据已经有序基准仍然接近数据中位数分区效果有保障。int medianOfThree(int arr[], int low, int high) { int mid low (high - low) / 2; if (arr[low] arr[mid]) swap(arr[low], arr[mid]); if (arr[low] arr[high]) swap(arr[low], arr[high]); if (arr[mid] arr[high]) swap(arr[mid], arr[high]); // 此时 arr[mid] 是三个数的中间值 return arr[mid]; }在partition中把mid位置的元素交换到low位置后再执行原有基于第一个元素的 Hoare 分区即可。6.3 小数组切换插入排序递归到末尾时子数组规模很小。此时快速排序的分区递归开销高于收益不如切换到插入排序。工程实践中的阈值通常在 10 到 20 之间。void quickSortOptimized(int arr[], int low, int high) { // 小数组使用插入排序 if (high - low 1 15) { for (int i low 1; i high; i) { int key arr[i]; int j i - 1; while (j low arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } return; } if (low high) { int pi partition(arr, low, high); quickSortOptimized(arr, low, pi); quickSortOptimized(arr, pi 1, high); } }很多语言标准库中的排序实现都采用了“快排 插入排序”的组合策略。Java 的Arrays.sort()对基本类型数组使用 Dual-Pivot QuickSort并且小数组走插入排序就是这个道理。6.4 三向切分当数组中存在大量重复元素时普通快速排序会把相同的值分到左右两侧导致分区不平衡。三向切分把数组分为小于基准、等于基准、大于基准三部分之后只需要递归处理小于区和大于区等于区直接跳过。荷兰国旗问题是经典的练习场。Dijkstra 提出的三向切分快速排序实现如下void quickSort3Way(int arr[], int low, int high) { if (high low) return; int lt low; int i low 1; int gt high; int pivot arr[low]; while (i gt) { if (arr[i] pivot) { swap(arr[lt], arr[i]); } else if (arr[i] pivot) { swap(arr[i], arr[gt--]); } else { i; } } quickSort3Way(arr, low, lt - 1); quickSort3Way(arr, gt 1, high); }面对包含大量重复键的数据比如按性别、按部门字段排序三向切分的性能优势非常明显。Sedgewick 曾在论文中指出对大量重复键的数组三向切分快速排序甚至可以达到线性时间复杂度。7. 复杂度分析与稳定性验证7.1 时间复杂度推导快速排序的时间复杂度取决于分区是否平衡。最理想情况下每次分区都把数组分成等长的两半递归深度为 log₂n每一层需要处理 n 个元素因此时间复杂度为 O(n log n)。最坏情况下每次分区只去掉一个元素递归深度为 n每一层仍然处理近似 n 个元素时间复杂度为 O(n²)。随机化基准之后最坏情况概率降到极低。平均情况下即使基准不是精确的中位数比如每次都分成 1:9 的比例递推公式为 T(n) T(n/10) T(9n/10) O(n)从递归树角度分析每一层代价仍然是 O(n)总深度近似 log₁₀n结果依然是 O(n log n)。这说明快速排序对基准“不完美”的容忍度其实很高。7.2 空间复杂度分析快速排序是原地排序不需要额外数组存储排序结果额外空间主要消耗在递归调用栈上。平均递归深度为 O(log n)意味着栈帧数量是 O(log n)。但最坏情况下递归深度为 O(n)空间复杂度退化到 O(n)。对于超大数组这可能导致栈溢出解决思路包括随机化基准、三数取中以及将递归改写为显式栈的迭代版本。7.3 稳定性验证用一个简单例子验证“不稳定”属性。原始数组包含两条记录[张三: 30, 李四: 28, 王五: 30]按年龄排序。如果采用快速排序基准选择第一位的张三30分区之后两个 30 的相对位置可能发生改变比如王五可能被移到张三之前导致原本排在后面的王五跑到了前面。这就是不稳定排序的含义。若业务要求同分记录保持原有顺序需要使用稳定排序算法。8. 快速排序动画演示与可视化调试学习快速排序最好的方式是自己把每轮分区结果打印出来逐帧观察变化过程。这里给出一段 C 语言调试代码在每次交换和每次分区完成后打印数组状态。#include stdio.h int debugStep 0; void printArrayWithMark(int arr[], int size, int pos1, int pos2, const char *msg) { printf(%-20s [, msg); for (int i 0; i size; i) { if (i pos1 || i pos2) { printf([%d] , arr[i]); } else { printf(%d , arr[i]); } } printf(]\n); } void debugSwap(int arr[], int a, int b, int size) { int temp arr[a]; arr[a] arr[b]; arr[b] temp; printf(交换 arr[%d]%d 和 arr[%d]%d\n, a, b, arr[a], arr[b]); printArrayWithMark(arr, size, a, b, 交换后); } int partitionDebug(int arr[], int low, int high, int size) { int pivot arr[low]; int i low - 1; int j high 1; printf(分区范围 [%d, %d]基准 %d\n, low, high, pivot); while (1) { do { i; } while (arr[i] pivot); do { j--; } while (arr[j] pivot); if (i j) { printf(左右指针相遇 i%d, j%d分区结束\n, i, j); return j; } debugSwap(arr, i, j, size); } } void quickSortDebug(int arr[], int low, int high, int size) { if (low high) { int pi partitionDebug(arr, low, high, size); printf( 分区索引 %d当前数组状态\n, pi); printArrayWithMark(arr, size, -1, -1, 本轮结果); quickSortDebug(arr, low, pi, size); quickSortDebug(arr, pi 1, high, size); } }将这段代码集成到主程序中就可以像动画每帧一样观察排序的推进。自己在本地跑一遍配合前面的动画示意快速排序的执行过程会比只看代码清晰很多。如果想生成图形动画可以用 Python 的matplotlib.animation。基本思路是先记录快速排序过程中每次交换后的数组快照再用动画帧逐个渲染这些快照。核心代码可以这样写import matplotlib.pyplot as plt import matplotlib.animation as animation def partition_record(nums, low, high, records): pivot nums[low] i low - 1 j high 1 while True: i 1 while nums[i] pivot: i 1 j - 1 while nums[j] pivot: j - 1 if i j: return j nums[i], nums[j] nums[j], nums[i] # 记录每一次交换后的数组快照 records.append(nums.copy()) def quicksort_record(nums, low, high, records): if low high: pi partition_record(nums, low, high, records) quicksort_record(nums, low, pi, records) quicksort_record(nums, pi 1, high, records) arr [49, 38, 65, 97, 76, 13, 27, 49] records [arr.copy()] quicksort_record(arr, 0, len(arr) - 1, records) fig, ax plt.subplots() colors [#3B82F6] * len(arr) def update(frame): ax.clear() ax.bar(range(len(records[frame])), records[frame], colorcolors) ax.set_title(f快速排序动画演示 - 第 {frame} 帧) ax.set_xlabel(索引) ax.set_ylabel(值) ani animation.FuncAnimation(fig, update, frameslen(records), interval500, repeatFalse) plt.show()运行上面这段脚本会弹出窗口逐帧播放快速排序的交换过程跟踪排序如何一步步推进。用动画辅助学习算法是效率比较高的方式。9. 快速排序代码常见错误与排查写快速排序时最容易出错的几个地方非常集中。把这些问题提前列出来写代码时可以有效避坑。问题现象可能原因排查方式解决方案程序递归后栈溢出崩溃基准选取导致分区严重失衡递归深度接近 n打印每次分区后的左右边界使用随机化基准或三数取中法死循环程序无法结束分区代码中arr[i] pivot和arr[j] pivot的条件写错导致指针越界后无法交叉检查 while 循环边界关系和轴点相同元素的处理逻辑使用和时注意i j的退出判断排序结果部分正确分区返回值边界理解错误Hoare 分区返回 jLomuto 分区返回 i1打印分区索引 pi验证基准是否归位Hoare 用low, piLomuto 用low, pi - 1数组越界partition中i和j缺少边界保护检查扫描循环是否在极限位置停止do-while 先自增自减的方式可避免一大部分越界大量重复元素时性能骤降普通分区对相等元素处理不好测试全等数组的排序耗时使用三向切分快速排序小数组性能反而慢递归函数调用开销大于直接插入对比 10 到 50 个元素的排序耗时小数组切换插入排序最值得反复检查的地方是分区函数的返回值和递归边界。Hoare 分区和 Lomuto 分区的写法完全不同绝对不能混用。从代码结构来看Hoare 分区内部用双指针交替扫描而 Lomuto 分区用单指针遍历配合i记录小于区末尾。9.1 递归深度过大的排查一个 10 万级的接近有序数组如果使用固定第一个元素为基准的快速排序递归深度可能接近 10 万程序会直接爆栈。排查方式是在quickSort函数入口打印low和high。// 在递归函数的第一行加入调试代码 printf(quickSort called: low%d, high%d\n, low, high);如果发现左边界一直比右边界小 1说明每次分区都几乎只减少一个元素基准选取策略需要调整。改用随机基准后接近有序数组依然可以得到接近 O(n log n) 的性能。9.2 稳定性和复杂度测试验证排序正确性的代码可以写成一个通用测试函数#include stdio.h #include stdlib.h #include time.h #include stdbool.h bool isSorted(int arr[], int n) { for (int i 1; i n; i) { if (arr[i - 1] arr[i]) { return false; } } return true; } void testQuickSort() { int n 10000; int *arr (int *)malloc(n * sizeof(int)); srand(time(NULL)); for (int i 0; i n; i) { arr[i] rand() % 10000; } quickSort(arr, 0, n - 1); if (isSorted(arr, n)) { printf(排序正确: 10000 个随机元素已有序\n); } else { printf(排序错误!\n); } free(arr); }在本地把测试数据量提升到 10 万、100 万可以直观感受快速排序在平均情况下的执行效率也能验证随机化基准的性能改进效果。10. 大数据量排序实测思路与性能对比快速排序的性能与数据分布关系很大。测试时可以准备三类数据完全随机数据、接近有序数据、包含大量重复值的数据。在这三类数据上分别观察耗时和递归深度。对于随机数据普通快速排序通常表现很好。对于接近有序的数据固定基准的快速排序会明显变慢而随机化基准能稳住性能。对于大量重复数据三向切分是有效的解法。如果对比归并排序和快速排序随机大数组场景下快速排序通常表现更好因为不需要额外开辟大块内存。但在链表排序场景下归并排序更合适因为链表随机访问代价高快速排序需要反复遍历链表性能不理想。如果目标是搜索“第 K 大元素”而不需要全排序基于快速排序分区思想的快速选择算法可以做到平均 O(n)。这是快速排序思想在排序之外的典型应用延伸。模板代码如下int quickSelect(int arr[], int low, int high, int k) { if (low high) { int pi partition(arr, low, high); if (pi k) return arr[pi]; else if (pi k) return quickSelect(arr, low, pi - 1, k); else return quickSelect(arr, pi 1, high, k); } return -1; }注意这里需要 Lomuto 分区的变体来保证返回位置准确指向分区后的索引。11. 各语言经典标准库排序参考语言标准库方法底层实现说明Cqsort()通常为快速排序实现但 C 标准不强制指定算法需要传入比较函数指针可用于任意类型数组Cstd::sort()Introsort内省排序混合快排、堆排和插入排序绝大多数情况下无需手写排序Java 基本类型Arrays.sort()Dual-Pivot QuickSort双轴快排相比经典快排有更好性能Java 引用类型Arrays.sort()TimSort归并排序的优化变种稳定排序适合对象排序Pythonsorted()/.sort()TimSort稳定排序C 语言实现性能稳定Gosort.Slice()pdqsort从 Go 1.19 起模式识别 快排混合C 语言的qsort是一个通用接口因为需要通过函数指针比较任意类型数据调用开销比直接写死int比较的快速排序大一些但工程中非常实用。这里展示一个完整示例#include stdio.h #include stdlib.h int compare(const void *a, const void *b) { return (*(int *)a - *(int *)b); } int main() { int arr[] {49, 38, 65, 97, 76, 13, 27, 49}; int n sizeof(arr) / sizeof(arr[0]); qsort(arr, n, sizeof(int), compare); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); return 0; }C 的std::sort是最常用的排序入口。它综合了多种排序策略保证平均时间复杂度 O(n log n)绝大多数情况下不需要自己实现排序#include algorithm #include iostream #include vector int main() { std::vectorint arr {49, 38, 65, 97, 76, 13, 27, 49}; std::sort(arr.begin(), arr.end()); for (int num : arr) { std::cout num ; } std::cout std::endl; return 0; }了解标准库底层实现的意义在于手写快速排序之前一定要先想清楚使用场景。如果只是工程中需要排序调用标准库最稳妥如果你在准备笔试、面试或者需要自定义排序逻辑理解快速排序及其变体依然重要。12. 总结与下一步练习方向这次把快速排序从动画演示到 C 语言、Java、Python 三种实现做了全面拆解。快速排序最值得花时间理解的部分有三个分区过程中基准元素的归位逻辑、递归边界条件的写法、最坏情况的原因与优化思路。这三个点全都掌握快速排序基本就过关了。如果你还在面试准备阶段下一步建议按照这个顺序继续练习第一把 C 语言版和 Java 版代码分别在自己的电脑上运行一遍确认输出结果正确用断点或打印语句逐步观察每一轮分区结果。第二用随机化基准替换固定基准用接近有序的数组测试两种实现的速度差异。第三找一个包含大量重复数字的数组把三向切分版代码跑通对比普通快速排序的耗时。第四用 LeetCode 215数组中的第 K 个最大元素这道题练习用快速选择思想解决问题。最容易踩的坑是递归边界混淆。请把“Hoare 返回 j递归区间是[low, pi]和[pi 1, high]Lomuto 返回 i1递归区间是[low, pi - 1]和[pi 1, high]”这一条记到笔记里每次写完代码后都对着检查一遍。快速排序的工程价值远超“笔试算法”的范畴。Java 的Arrays.sort()用双轴快排C 的std::sort用内省排序Go 1.19 起用 pdqsort它们的思想源头都是快速排序。理解快速排序等于拿到了一把阅读标准库源码的钥匙。后面可以继续挑战堆排序和归并排序把这三种 O(n log n) 排序算法放在一起对比对排序问题的理解会更完整。建议收藏备用面试前翻一翻这段动画和代码对照效率很高。