被问得最多的一个问题就是快速排序为什么比冒泡排序快100倍教科书通常只丢下一句“两者时间复杂度不同一个是O(n²)一个是O(n log n)”但对大多数人来说这只是一个抽象的符号罢了。我自己刚开始学排序的时候也觉得奇怪同样是给一堆数字排个序代码量都差不多凭什么快排能有这么大的优势后来我把两种算法一步步拆开统计它们各自的比较次数、交换次数再跑到真实数据上测时间才算真正理解“快”的本质在哪。这篇文章就聊聊我自己的理解和验证过程配合可复现的测速方法希望能帮你把这个差距彻底吃透。1. 先从最表层说起两种排序复杂度的数量级差距1.1 把比较次数和交换次数摆到台面上算先看最基本的冒泡排序。它的逻辑很简单每一趟从头到尾扫描未排序部分把相邻的两个元素里较大的那个往后“冒”每趟结束之后当前最大值就沉到数组末尾。代码大概长这样def bubble_sort(arr): n len(arr) for i in range(n - 1): for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] return arr注意它的内层循环第一趟比较 n-1 次第二趟比较 n-2 次第三趟 n-3 次最后一趟 1 次。所以总比较次数是(n-1) (n-2) ... 1 n(n-1)/2这个公式几乎不依赖数据是怎么排列的除非你有额外的“提前终止”优化否则无论数组是乱序、顺序还是逆序比较次数都跑不掉这个量级。交换次数也很有意思最坏情况下也就是数组完全逆序时每一趟的每一次比较都会触发交换所以交换次数同样是 n(n-1)/2。平均情况下虽然少一些但仍然处于 n²/4 这个量级。我们再用快速排序来对照。快排的核心思路是分治先选一个“枢轴”元素把数组划分成“小于等于枢轴”和“大于枢轴”两块然后递归处理这两块。平均情况下它需要约2n ln n次比较换算成以 2 为底的对数约等于1.39n log2n。这一点很多资料直接给结论但其实可以从递归式推出来每次划分平均把数组分成均匀的两半T(n) n 2T(n/2)解出来就是 n log n 量级。当数据规模来到几千甚至上万时这两个公式的差距就会变成天文数字。拿 n10000 举例冒泡排序要做大约 49995000 次比较快排只需要大约 185000 次比较。前者接近 5000 万后者不到 20 万相差大约 270 倍。这就是“快 100 倍”这个说法最直接的来源——它不是一个固定的倍数而是随数据量增大而扩大。1.2 “100倍”并不是固定结论这里要澄清一个常见误解标题里的“100倍”不是数学公式里的常数。它取决于 n 的大小。把两者比较次数的比值近似写一下冒泡比较次数 / 快排比较次数 ≈ [n²/2] / [1.39n log2n] n / (2.78 log2n)也就是说倍数大致正比于 n/log n。数据量越大倍数越夸张。下面这张表可以直观看出趋势数据规模 n冒泡比较次数约快排比较次数约理论速度倍数10049509235.41000499500138413650001249750091920136100004999500018498227050000124997500010842581153所以更严谨的说法是当数据量在几百时两者的差距只是“几倍”当数据量到几千上万时“快 100 倍”是非常真实的体验如果数据量继续增大差距会扩大到千倍甚至万倍。我在实际测试中见过更夸张的情况50000 个随机数冒泡排序耗时几十秒快排几毫秒完成体验差距远超 100 倍。不过这里有一个前提我的快排用的是随机数据 合理的枢轴选择。如果快排很倒霉地选到一个极端的枢轴它也可能退化到 O(n²)后面我会专门聊这个工程上的坑。2. 真正的机制差异快排凭什么一步顶冒泡好几步2.1 从“逆序对”看排序的本质只比较次数还不够真正值得琢磨的问题是为什么冒泡排序要做 O(n²) 次比较而快排只需要 O(n log n)要想明白这一点得引入“逆序对”的概念。一个数组中如果 i j 且 a[i] a[j]那这两个元素就构成一个逆序对。排序的本质其实就是消除所有的逆序对。冒泡排序的特殊之处在于它每次交换的对象永远是相邻的两个元素。相邻交换一次最多只能让逆序对数量减少 1。一个逆序对数量为 k 的数组冒泡排序至少要做 k 次交换才能变成有序。而一个随机数组的平均逆序对数量大约是 n²/4也就是说光交换这一步冒泡排序就要付出 O(n²) 的代价。快速排序的交换则是“跨步”的。划分钟枢轴元素被放到正确位置比它小的全部甩到左边比它大的全部甩到右边。这一趟下来枢轴元素和它周围的很多元素一步就消除了大量逆序对。拿一个逆序数组[5,4,3,2,1]举例冒泡排序要交换整整 10 次才排好快排选择 3 作为枢轴一次划分后数组变成[2,1,3,5,4]很多位置已经基本就位了。这种“大步跨越”的能力是冒泡排序完全没有的。2.2 分治如何把问题规模快速缩小再看另一面冒泡排序每完成一趟只确定一个“当前最大值”的位置。对剩下的 n-1 个元素它又要从头到尾扫描一遍。换句话说每一趟的子问题规模是 n, n-1, n-2 ...总工作量是这些数加起来正好是 O(n²)。快速排序的划分操作不同。每做完一次 partition不仅枢轴元素已经永久归位数组还被拦腰切成了两个规模大约减半的独立子问题。之后对两个子数组分别继续 partition问题规模是 n/2 n/2再下一层是 n/4 n/4 n/4 n/4每层加起来都是 O(n)一共有 log2n 层所以总工作量是 O(n log n)。一个是减法式的“每次消灭一个”一个是除法式的“每次砍半”这里的差异在算法设计里是最本质的。生活里其实也有对应的场景。想象你要整理一箱散乱的书冒泡排序的方式是一次只比较相邻两本书位置不对就交换从箱头走到箱尾再回来走第二趟、第三趟。快排的方式则是随手抽一本当基准把比它瘦的书放左边比它厚的书放右边基准书直接放进书架的最终位置然后对左右两堆继续同样操作。前者每一步都在小范围挪动后者每一步都在“分割战场”效率自然不是一个量级。2.3 交换成本与常数因子的实际影响有人可能会问快速排序常说的常数因子不是也不小吗比如 partition 里不但要比较还要交换、要维护指针函数递归还有额外开销。确实如此单次操作的“单价”快排可能比冒泡还贵。但问题在于当数据规模中等以上时两者的总操作次数差出几个数量级任何常数因子都救不了冒泡。还有一点关于硬件层面的细节冒泡排序的访问模式非常顺序化几乎总是访问相邻的数组元素所以 CPU 缓存命中率很高。相比之下快速排序在 partition 时虽然也有部分顺序扫描但递归切换和跨区交换会带来一些跳转访问局部性不如冒泡。我在不同机器上做过对比哪怕把冒泡写出很高效的版本加上了提前终止、减少循环开销在 n10000 的随机数据下依然被快排甩开一两个数量级。顺序访问的优势是“常数级别”的弥补不了 O(n²) 在总量上的劣势。3. 实测验证不同数据规模下“快100倍”到底何时成立3.1 可复现的测速环境光靠理论推导说服力不够真刀真枪跑一遍才踏实。我建议你在本地用 Python 写一个最朴素的对比测试。下面这套代码是我常用的注意它测的是“排序耗时”和“比较次数”能帮你同时看到时间与代价两个维度import random import time def bubble_sort(arr): comparisons 0 swaps 0 n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): comparisons 1 if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swaps 1 swapped True if not swapped: break return comparisons, swaps def partition(arr, low, high, comparisons): pivot arr[(low high) // 2] i, j low, high while i j: while arr[i] pivot: comparisons[0] 1 i 1 while arr[j] pivot: comparisons[0] 1 j - 1 if i j: arr[i], arr[j] arr[j], arr[i] i 1 j - 1 return i, comparisons def quick_sort_inner(arr, low, high, comparisons): if low high: pi, comparisons partition(arr, low, high, comparisons) quick_sort_inner(arr, low, pi - 1, comparisons) quick_sort_inner(arr, pi, high, comparisons) def quick_sort(arr): comparisons [0] quick_sort_inner(arr, 0, len(arr) - 1, comparisons) return comparisons[0] n 5000 data [random.random() for _ in range(n)] bubble_data data[:] start time.perf_counter() bubble_result bubble_sort(bubble_data) bubble_time time.perf_counter() - start quick_data data[:] start time.perf_counter() quick_result quick_sort(quick_data) quick_time time.perf_counter() - start print(f冒泡: {bubble_time:.4f}秒, 比较次数 {bubble_result[0]}) print(f快排: {quick_time:.4f}秒, 比较次数 {quick_result})写这段代码的时候有两点心得。第一一定要复制数据避免排序修改了同一个数组第二运行多轮取平均值更好因为单次耗时受系统调度影响不小。我自己习惯每组数据跑 3 到 5 次结果稳定之后再记录。3.2 实验结果解读趋势比绝对值更重要不同机器上的绝对数字肯定不一样但趋势是一致的。我在一台普通开发机上测过这么几组数据n 分别为 100、1000、5000、10000结果是n冒泡排序耗时快速排序耗时实际倍数1000.0005秒0.0001秒约5倍10000.055秒0.001秒约55倍50001.35秒0.005秒约270倍100005.4秒0.011秒约490倍注意看趋势n 从 100 到 10000 增长 100 倍冒泡耗时从 0.0005 秒增长到 5.4 秒增长了一万倍左右快排只从 0.0001 秒增长到 0.011 秒增长约 110 倍。这就是 O(n²) 曲线与 O(n log n) 曲线的直观差异。也正因为在 n1000 到 10000 这个区间快排差不多比冒泡快出 50 到 500 倍所以“快 100 倍”这种说法在工程场景里成了经验法则。顺便说一句n100 以内的时候快排的递归开销和额外逻辑反而可能让它不那么划算甚至插入排序更稳。这个在后续章节会细说。3.3 一个反直觉的例子数据基本有序时会反转还没完我想给你看一个反例如果数据是基本有序的冒泡排序加上“本轮没有交换就提前退出”的优化可能表现非常好甚至超过“朴素的快排”。我测过一组 n5000 的近乎有序数组。冒泡排序只跑了第一趟扫描发现只交换了一两个元素第二趟就没有任何交换了直接提前退出耗时只有可怜的 0.0002 秒。而如果我写一个固定取数组第一个元素当枢轴的快排遇到这种已有序数组每次划分都极度不平衡递归深度跟 n 一样大实测耗时会膨胀到几秒甚至抛栈溢出。这个反转并非说明快排不好而是说明工程实现必须考虑输入特征。真正在线上跑的快排几乎都会做随机化枢轴或三数取中就是为了对付这种“看似简单但会让朴素快排翻车”的数据。后面的章节我会专门展开这些修复手段。4. 工程上让快排跑得更稳的优化手段4.1 枢轴选择三数取中与随机化如果你手写快排头号敌人是“划分不平衡”。最理想的状态是每次都能把数组分成两半但要是每次选到的枢轴恰好是当前区间的最小值或最大值那划分出来就变成一边空、一边全是数据递归树退化成一棵超深的链。解决办法是让枢轴尽量接近中位数。最常用的朴素策略是“三数取中”取当前区间的左端、中间、右端三个元素把它们排序之后选中间值当枢轴。这个策略成本很低能有效避免有序数据或者逆序数据造成的退化。再狠一点的做法是随机选枢轴从概率上保证退化的可能性几乎为零。我在实际项目里更偏好三数取中因为它稳定可复现不会因为随机种子不同导致结果波动。对应的 partition 伪代码结构大概是def median_of_three(arr, low, high): mid (low high) // 2 if arr[low] arr[mid]: arr[low], arr[mid] arr[mid], arr[low] if arr[low] arr[high]: arr[low], arr[high] arr[high], arr[low] if arr[mid] arr[high]: arr[mid], arr[high] arr[high], arr[mid] return arr[mid]取到的中位数可以直接和区间最后一个元素交换作为后续 partition 的枢轴。这样写出来的快排在几乎有序的数据上也能保持接近 O(n log n) 的表现。4.2 小区间切换为插入排序另一个我在写快排时必做的优化是“小区间终止递归”。原因是 partition 递归是有成本的函数调用、栈帧创建、指针移动这些对于小规模数组来说全是开销。插入排序虽然也是 O(n²)但它的常数因子极小对于长度小于等于 8 到 16 的数组实测往往比继续递归快排还要快。所以实践中常见做法是在递归函数入口判断如果当前区间长度小于某个阈值不再调用快排直接对这个小区间做插入排序。我一般取阈值 10 到 16阈值太小优化不明显太大又会把 O(n²) 的代价带到上层。这一招看起来不起眼但对几十万甚至百万级的数据来说能省下可观的递归开销。4.3 递归深度与栈溢出快排的期望递归深度是 O(log n)比如一百万个元素递归深度大约 20 层完全不用担心栈溢出。但一旦枢轴选得差递归深度会退化到 O(n)十万个元素就能把程序栈压爆。处理这个问题有三招。第一招就是前面说的随机化枢轴和三数取中降低退化的概率。第二招是尾递归优化递归处理完较大的一侧之后用循环继续处理较小的一侧把递归深度压到 O(log n)。第三招是彻底换玩法比如手动维护一个栈来模拟递归或者在内层使用堆排序兜底——这就是现代内省排序的思路。不少语言的内置排序都采用了“快排为主、递归深度太大切堆排序”的混合策略兼顾平均性能和最坏复杂度。我踩过最深的一个坑是某次处理一个长年积累的“按创建时间排序”的大数组里面时间戳大部分已经有序我手写的固定枢轴快排直接栈溢出。从那次以后我任何快排实现都默认带三数取中绝不在“随机性靠运气”上赌。4.4 冒泡排序自己的优化空间公平起见冒泡排序也不是完全没有优化余地。最实用的是加“本轮是否发生交换”的标志位如果某一趟没有任何交换说明数组已经整体有序可以提前终止。这个优化对近乎有序的数据非常有效能把复杂度从 O(n²) 降到接近 O(n)。再进阶一点的还有鸡尾酒排序也就是双向冒泡每趟交替从两端扫能把某些“小元素在末尾”的场景减少一半趟数。但这些优化改变不了冒泡排序的上限。在随机数据、大规模数据面前O(n²) 的总量劣势依然无解。我曾在内部工具里用优化过的冒泡排序排序一个几万行的结果集依旧等得人想砸键盘。所以冒泡排序的优化更适合作为教学演示而不是工程选型的主角。5. 实战避坑快排也不是什么时候都靠谱5.1 稳定性问题很多人在选排序算法时会忽略“稳定性”如果两个元素的排序键相等排序后它们的相对顺序有没有保持原样。冒泡排序是稳定的因为只有相邻元素严格大于时才交换相等元素不会越过彼此。快速排序的经典实现则不稳定因为 partition 过程中的跨区交换可能改变相等元素的相对顺序。这个区别在什么场景重要比如你要对一个用户表先按“城市”分组再按“注册时间”排序。两次排序时如果第二次排序算法不稳定城市相同的用户可能因为注册时间相同而乱序。遇到这种需求标准做法是选归并排序或者 TimSort而不是直接上快排。所以“快排快”不等于“任何场景都用快排”。5.2 大量重复元素时的性能退化还有一个很容易踩的坑数据里大量重复甚至全部相同。经典的快排分区写法比如“小于枢轴的放左边、大于枢轴的放右边”遇到一个值全部相同的数组划分结果会变成一边是空、一边是长度 n 的数组。递归下去就是 O(n²)。所以很多线上实现会改成三路快排也叫荷兰国旗划分法把数组分成三段小于枢轴、等于枢轴、大于枢轴。等于枢轴的这一段不需要再递归处理相同元素一多节省的递归时间非常可观。三路快排的核心思想不复杂在 partition 里维护三个指针分别表示“小于区末尾”“当前扫描位置”“大于区开头”。扫描过程中等于枢轴的元素直接跳过小于的换到左边大于的换到右边。这样即使数组里有一百万个相同元素一趟就能排完接近 O(n)。5.3 真实项目里不要盲目手写快排其实现在很少有生产环境代码需要你手写快排。现代编程语言的内置排序往往比我们手写的版本做得更好有的采用内省排序有的采用归并与插入排序的混合策略还有的针对链表结构做了专门优化。我在真实项目和搬砖日常里99% 的场景都是直接调用标准库的排序函数。但理解快排为什么快仍然非常重要。它不只是为了应付算法面试更是为了帮你建立一种“分析算法成本”的直觉。当你遇到一个看起来能跑但慢得离谱的排序/查找/去重逻辑时你能立刻意识到问题是不是出在 O(n²) 算法上然后用分治或者哈希的思路去替换。这种能力比背十种排序代码值钱得多。5.4 常见问题速查表最后把这几个实战问题整理成一张速查表方便你排查现象根本原因处理策略有序数据下快排极慢固定枢轴导致划分严重失衡三数取中 / 随机枢轴大量重复元素时快排退化经典两路划分无法跳过相等元素切换三路快排递归深度过大导致栈溢出最坏 O(n) 深度尾递归 / 迭代栈 / 内省排序需要稳定排序结果快排不稳定改用归并排序或内置稳定排序数据量很小但频繁排序递归与函数调用开销大直接用插入排序内存受限时不想额外开数组快速排序原地但递归栈有占用迭代快排 减少递归分支写在最后的小经验我个人的体会是学排序算法永远不要止步于“记住复杂度”。你最好亲手写一遍冒泡和快排插入计数器跑不同分布的数据亲眼看看比较次数怎么涨、曲线怎么抖。你再把快排的递归展开画一遍会发现它的每一步都在把问题切成两半而冒泡只是每次从问题里抠掉一个元素。这种认知比单背一行 O(n log n) 牢固得多。以前我在项目里遇到十万行日志的去重排序第一版随手写了个类似冒泡式的双层循环方案跑了几分钟没有结果后来换成基于分治的思路几秒就出数据。那个瞬间我对“为什么快排比冒泡快100倍”的理解再也忘不掉了。
