快速排序比冒泡排序快100倍？复杂度、原理与实测揭秘

被问得最多的一个问题就是：快速排序为什么比冒泡排序快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 量级。

当数据规模来到几千甚至上万时，这两个公式的差距就会变成天文数字。拿 n=10000 举例：冒泡排序要做大约 49995000 次比较，快排只需要大约 185000 次比较。前者接近 5000 万，后者不到 20 万，相差大约 270 倍。这就是“快 100 倍”这个说法最直接的来源——它不是一个固定的倍数，而是随数据量增大而扩大。

1.2 “100倍”并不是固定结论

这里要澄清一个常见误解：标题里的“100倍”不是数学公式里的常数。它取决于 n 的大小。把两者比较次数的比值近似写一下：

冒泡比较次数 / 快排比较次数 ≈ [n²/2] / [1.39n log2n] = n / (2.78 log2n)

也就是说，倍数大致正比于 n/log n。数据量越大，倍数越夸张。下面这张表可以直观看出趋势：

所以更严谨的说法是：当数据量在几百时，两者的差距只是“几倍”；当数据量到几千上万时，“快 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 时虽然也有部分顺序扫描，但递归切换和跨区交换会带来一些跳转访问，局部性不如冒泡。我在不同机器上做过对比，哪怕把冒泡写出很高效的版本，加上了提前终止、减少循环开销，在 n=10000 的随机数据下依然被快排甩开一两个数量级。顺序访问的优势是“常数级别”的，弥补不了 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 从 100 到 10000 增长 100 倍，冒泡耗时从 0.0005 秒增长到 5.4 秒，增长了一万倍左右；快排只从 0.0001 秒增长到 0.011 秒，增长约 110 倍。这就是 O(n²) 曲线与 O(n log n) 曲线的直观差异。也正因为在 n=1000 到 10000 这个区间，快排差不多比冒泡快出 50 到 500 倍，所以“快 100 倍”这种说法在工程场景里成了经验法则。

顺便说一句，n=100 以内的时候，快排的递归开销和额外逻辑反而可能让它不那么划算，甚至插入排序更稳。这个在后续章节会细说。

3.3 一个反直觉的例子：数据基本有序时会反转

还没完，我想给你看一个反例：如果数据是基本有序的，冒泡排序加上“本轮没有交换就提前退出”的优化，可能表现非常好，甚至超过“朴素的快排”。

我测过一组 n=5000 的近乎有序数组。冒泡排序只跑了第一趟扫描，发现只交换了一两个元素，第二趟就没有任何交换了，直接提前退出，耗时只有可怜的 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 log n) 牢固得多。以前我在项目里遇到十万行日志的去重排序，第一版随手写了个类似冒泡式的双层循环方案，跑了几分钟没有结果；后来换成基于分治的思路，几秒就出数据。那个瞬间我对“为什么快排比冒泡快100倍”的理解，再也忘不掉了。