排序算法复杂度精讲：从O(n²)到O(n log n)的工程选型

1. 先想明白一件事：排序算法的复杂度分析到底在分析什么

1.1 排序不是背代码，是训练“数据规模直觉”

很多朋友学排序算法，第一反应是背代码：冒泡怎么写，快排怎么写，堆排怎么写。背完能过面试，但过不了实战。因为真实工程里几乎不会让你手写一个排序算法，你更多是在做三件事：选对现成的排序、判断当前数据量是否会导致性能问题、以及理解某个排序行为为什么不符合预期。

这三件事，靠的全是对复杂度分析的理解，不是代码肌肉记忆。

复杂度分析本质上回答一个问题：当数据量翻倍、翻十倍、翻一百倍的时候，这个算法的时间会怎么变？

• O(n)：数据量翻倍，时间约翻倍，线性增长，很友好。
• O(n log n)：数据量翻倍，时间变得比两倍稍多一点，但仍在可控范围。
• O(n²)：数据量翻倍，时间变成四倍，数据量翻十倍，时间变成一百倍。这是灾难。

我习惯用一个特别土的数字例子给自己找感觉：假设排序 1000 个数据，O(n log n) 的算法用了 1 毫秒，那数据变成 100 万时，大约会用到 1ms × 2000 / 1000 × log(1000)? 不对，直接粗暴估算：数据量放大 1000 倍，n log n 大概放大 1000 × log(10³)/log(10)? 其实不用算那么精细，你只要记住：O(n²) 到 100 万数据，粗略要做一万亿次基本操作，而 O(n log n) 大概只需要两千万次，差了五个数量级。这就是为什么算法课上的“复杂度”不是期末考试用一下就扔的东西，它是你对程序性能能否扛住将来数据增长的底层直觉。

1.2 时间复杂度、空间复杂度、稳定性的三角关系

我们常说的“复杂度分析”，在排序语境下通常指三样东西：时间复杂度、空间复杂度、稳定性。这三样不是并列关系，而是两个硬指标加一个软属性。

时间复杂度里又分最好、最坏、平均。很多排序算法的复杂度会随输入数据的初始顺序剧烈波动。比如插入排序，对一个已经有序的数组，复杂度能降到 O(n)，而快速排序对一个几乎有序的数组，如果选枢轴的策略不好，能退化到 O(n²)。所以你看“快速排序复杂度 O(n log n)”这句话其实是不完整的，准确说法是“平均 O(n log n)，最坏 O(n²)，通过随机化或三数取中可以大幅降低最坏情况发生的概率”。

空间复杂度指的是额外内存。原地排序的额外空间是 O(1)，归并排序需要 O(n) 的辅助数组，堆排序又是 O(1)。别小看空间复杂度，在嵌入式环境或处理超大数组时，O(n) 的辅助空间有时候比时间更重要。

稳定性这个概念很多人会忽略，但它才是工程里最常被问到“为什么排序结果不稳定”的根源。稳定性的意思是：如果两个元素值相等，排序后它们的相对顺序能不能保持原样。冒泡、插入、归并能做到稳定；选择、希尔、快排不稳定。后面我会专门展开讲，这里先记住：稳定性不是“算法好不好”的指标，而是“业务是否需要”的指标。

2. 三个 O(n²) 老朋友：冒泡、选择、插入的脾气各不相同

2.1 冒泡排序：理论最直观，实战最容易优化到变形

冒泡排序的思路一句话就能说清：从左往右不断比较相邻元素，如果顺序不对就交换，每一轮都会把当前剩余部分的最大值“冒”到最后面。

冒泡排序（基础版） 第1轮：依次比较 arr[0] vs arr[1]，arr[1] vs arr[2] ... 最大的元素一路交换到最后 第2轮：继续从头开始，但不用管最后一个位置 第二大的元素排到倒数第二位 ... 第n-1轮结束后，数组有序

复杂度很简单：外层循环 n-1 轮，内层每轮平均比较 n/2 次，总比较次数约 n²/2。所以最好、最坏、平均都是 O(n²)。注意这里有个隐藏问题：冒泡排序在最好情况下也是 O(n²)，除非你加了“本轮没有发生交换就提前结束”的优化。加上这个标记位之后，最好情况（数组已经有序）变成 O(n)，只需要跑一轮检查就退出。

我年轻的时候在某个模拟项目中用冒泡排过几万条记录，结果页面卡了好几秒，后来才发现问题不在数据量，而在没有提前退出。加了 flag 优化后又快了不少——虽然依然是 O(n²)，但常数小，对“基本有序”的数据很友好。

从交换次数看，冒泡排序每次发现逆序立刻交换，交换次数大约等于逆序对数。最坏时逆序对约为 n²/4，所以交换开销很大。这也是为什么冒泡在现代工程里几乎不直接使用，它更多是被当作“排序入门第一课”，用来帮助理解“比较、交换、轮次”这三个基本操作。

2.2 选择排序：交换次数最少的“老实人”

选择排序的思路也很直白：每一轮从待排序区间里挑出最小值，放到最前面。

选择排序 第1轮：在整个数组中找出最小值，与 arr[0] 交换 第2轮：在 arr[1..n-1] 中找出最小值，与 arr[1] 交换 ... 第n-1轮结束

它的比较次数和冒泡一样，都是 n²/2 量级，但交换次数只有 O(n)，因为每一轮只做一次交换。如果“写操作”比“读操作”贵很多（比如元素是大对象，或者交换需要触发缓存失效），选择排序反而比冒泡占优。

但选择排序有一个非常让人无语的特性：它不稳定。举一个三元素例子：

输入: [5a, 3, 5b, 1] 第1轮找到最小值 1，与 5a 交换 结果: [1, 3, 5b, 5a]

原来 5a 在 5b 前面，排序后 5a 跑到 5b 后面去了。因为“把最小值挪到前面”这个动作会跨越中间元素，直接破坏相等元素的相对顺序。

我对选择排序的评价是：学它主要为了理解“每轮挑选最值”这个思想，以及作为“交换次数极少”的一个案例。实际开发中，你几乎不会单独用它，但如果手头没有现成排序库，且数据量很小、交换成本又特别高，它也不是不能应急。

2.3 插入排序：小规模数据里真正的王者

插入排序的思路和整理扑克牌一模一样：从第 2 张开始，把当前牌往已经排好序的牌堆里插，插入过程中把比它大的牌往后挪。

插入排序 第1轮：arr[0] 视为已排序 第2轮：arr[1] 与其前面比较，插到合适位置 第3轮：arr[2] 插入前两个元素之间 ... 第 n-1 轮完成

复杂度分析是最有趣的地方：

• 最好情况：数组已经有序，每轮只需要比较一次，总时间 O(n)。
• 最坏情况：数组逆序，每轮要挪动所有已排序元素，O(n²)。
• 平均情况：O(n²)，但常数很小。

为什么插入排序值得单独表扬？因为它在“基本有序”的小规模数据上表现极佳，而且它是稳定的。很多现代排序库的底层混合策略里，插入排序依然被用来收尾。比如快速排序递归到小区间时，不再继续递归，而是改用插入排序，因为递归的调用开销和数据量小的常数开销反而超过插入排序。我自己实测过，16 个元素以内，插入排序往往能跑赢快排的递归版，这是真实的常数项差距。

2.4 三者对照：什么时候该用它们

算法	最好	最坏	平均	空间	稳定性
冒泡	O(n)（优化版）	O(n²)	O(n²)	O(1)	稳定
选择	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入	O(n)	O(n²)	O(n²)	O(1)	稳定

从这张表能提炼出一个工程结论：O(n²) 的排序并非一无是处。插入排序在 n 小于几十时，配合它优秀的稳定性，常常是混合排序中的“收尾组件”。冒泡和选择则更多承担教学价值，直接使用的场景极少。

3. 希尔与归并：离开 O(n²) 的两条路

3.1 希尔排序：一次“分组插入”的跨界尝试

希尔排序是在插入排序基础上的改进，核心思想是：先让数组“大致有序”，再做最后的插入排序。怎么做到大致有序？把相隔某个“增量 gap”的元素看成一组，对组内做插入排序，然后逐渐缩小 gap，直到 gap = 1。

希尔排序（gap 序列示例：5, 2, 1） gap = 5：对索引差为 5 的元素分组，组内插入排序 gap = 2：对索引差为 2 的元素分组，组内插入排序 gap = 1：对整个数组做标准插入排序

为什么要这样设计？因为插入排序最怕“小元素在很后面”，每次只能挪一步，效率极差。希尔排序通过大步长，让小元素能快速“跨步”往前跳，减少整体挪动次数。

希尔排序的复杂度比较微妙，它取决于 gap 序列的选择。常见结论：

• 简单 gap 序列（比如每次除以 2）：最坏 O(n²)。
• 某些精心设计的 gap 序列：最坏可以做到 O(n^(3/2))，甚至更好。

希尔排序不稳定，因为分组插入会导致相同值的相对顺序被打乱。它现在在实战中并不多见，但我认为它值得学，因为它第一次让初学者看到“改进一个基础算法”的思路：不要小看插入排序，只要先减少逆序对，它就能脱胎换骨。这种从基础出发做优化的思维，比背一个高级算法有用得多。

3.2 归并排序：把排序变成合并两个有序数组

归并排序的思路是分治：把数组从中间劈成两半，分别排好，然后合并两个有序数组。合并时只要不断比较两个数组的头部元素，把较小的拿出来，就能得到整体有序的结果。

归并排序（递归版） 1. 如果区间长度 <= 1，直接返回 2. 中点 mid = (left + right) / 2 3. 对 [left, mid] 递归排序 4. 对 [mid+1, right] 递归排序 5. 合并两个有序子区间

合并操作的复杂度是 O(n)，因为两个有序数组各扫一遍。递归深度是 log n，每层的总合并复杂度是 O(n)，所以总复杂度稳定在 O(n log n)，不管输入顺序如何。这是归并排序最大的优点：没有最坏情况，天然稳定。

代价是空间复杂度 O(n)。合并时需要一个临时数组来承载结果。递归深度虽然只有 log n 层，但每层分配和拷贝数组也有不小的常数开销。如果数据是链表，归并排序反而很合适，因为链表不需要额外连续空间，只需要指针操作。

3.3 归并排序的工程代价：空间与递归

我在实际项目里见过不少手写归并的人，最常踩的坑是临时数组在递归中频繁创建。正确做法是：在递归入口外只创建一个临时数组，递归过程中反复复用同一个临时数组，而不是每层都 new 一个新数组。否则空间复杂度虽然理论是 O(n)，实际分配开销会严重拖慢性能。

另一个值得注意的点是：归并排序适合对稳定性有硬性要求的场景。比如按姓名排序后，再按部门排序，如果部门相同的人还希望保留姓名顺序，那就必须用稳定排序。这时候归并排序几乎是唯一“稳定且 O(n log n)”的选择。

4. 快排与堆排：两种“接近最优”的排法，性格完全不同

4.1 快速排序的灵魂：枢轴选得好不好，决定复杂度

快速排序也是分治思想，但它和归并不一样：快排先把数组“分”成左右两半，左边都小于等于某个基准值（枢轴），右边都大于等于它，然后再递归分别排序。归并的“合并”发生在递归返回之后，快排的“划分”发生在递归深入之前。

快速排序（以最左元素为枢轴的基础版） 1. 选一个枢轴 pivot = arr[left] 2. 把数组划分成三部分：<= pivot | pivot | >= pivot 3. 对左半递归排序 4. 对右半递归排序

平均情况下，每次划分都能把数组大致分成两半，递归深度 log n，每层划分 O(n)，所以平均复杂度 O(n log n)。最坏情况下，如果每次枢轴都是当前区间的最大值或最小值，划分结果变成 0 对 n-1，递归深度变成 n，复杂度退化成 O(n²)。

最经典的退化场景就是：对一个已经有序的数组，每次取最左边元素当枢轴，结果每次都只消掉一个元素。解决办法有很多：取中间值、随机选枢轴、三数取中。这也是为什么学快排不能只记代码，必须理解枢轴选择对复杂度的致命影响。

4.2 堆排序：用堆这种结构做到原地排序，但它不稳定

堆排序的思路是：先把数组建成最大堆，然后不断把堆顶（最大值）交换到数组末尾，缩小堆范围，再调整堆结构。这样不需要额外空间，在原数组上就能完成排序，空间复杂度 O(1)。

堆排序 1. 从最后一个非叶子节点开始，从下往上调整，建立最大堆 2. 交换 arr[0] 与 arr[n-1]，堆大小减 1 3. 对剩余堆做下沉调整 4. 重复第2、3步，直到堆大小为 1

堆排序的时间复杂度稳定 O(n log n)，建堆可以做到 O(n)，之后 n-1 次调整，每次 O(log n)，合计 O(n log n)。它没有快排那样的最坏退化风险，也不需要归并那样的额外空间，看起来很美，但实际表现却往往不如快排。

原因在于“常数项”。堆排序的下沉调整，每一步要在子节点间比较两次，而且元素交换后，数组局部性很差，对现代 CPU 的多级缓存非常不友好。快排的划分过程是顺序扫描，缓存命中率高；堆排序则是大跨度跳跃访问，缓存命中率低。同样的 O(n log n)，实际速度可以差 2 到 3 倍。

堆排序还不稳定，即使建堆和调整的过程中没有刻意打乱相等元素，堆顶交换到末尾的动作也会破坏它们的相对顺序。

4.3 快排 vs 堆排 vs 归并：复杂度之外的真实差距

算法	平均时间	最坏时间	空间	稳定性	常数项	典型场景
快速排序	O(n log n)	O(n²)	O(log n)（递归栈）	不稳定	小	通用排序首选
堆排序	O(n log n)	O(n log n)	O(1)	不稳定	大	嵌入式、要求最坏有界
归并排序	O(n log n)	O(n log n)	O(n)	稳定	中	外部排序、稳定排序需求

我的理解是：这三者不是“谁取代谁”，而是各自占了一个象限。快排赢在平均性能和常数项；堆排赢在最坏情况有保证且不需要额外空间；归并赢在稳定和最优保证。工程里某一个开源语言的运行时排序实现，说白了就是“快排 + 插入排序 + 堆排序”的组合策略：数据量大时走快排，快排递归进入小区间改用插入排序，一旦检测到递归深度异常，马上切换成堆排序来兜底，确保最坏情况下不退化到 O(n²)。这个思路非常值得借鉴。

5. 复杂度数值之外，最容易翻车的几个细节

5.1 “最坏情况”是理论风险，不是纸上谈兵

很多人觉得快排最坏 O(n²) 就是个理论值，实际碰不到。直到我遇到一次线上问题：对某张表的某个字段排序，排序前数据刚好是经过另一个字段分组后有序的，而我们的快排实现取的是固定中间元素做枢轴，结果某个特定的数据分布让递归深度暴涨，耗时从几毫秒涨到几秒。

从那之后我养成了一个习惯：凡是手写快排或改造快排，一定用随机化枢轴或三数取中，并且设置递归深度阈值。如果你只是调用现成库，也要意识到“数据有序或近似有序”对算法选型的影响。比如对本来就接近有序的大数组，插入排序或定制化的 Timsort 类算法反而远比普通快排快。

5.2 稳定性排序在真实业务里的价值

稳定性听起来像学院派概念，但实际业务里经常用到。常见例子：商品列表先按销量排序，再按价格排序，用户希望“同价格下销量高的在前”。如果第二次排序是稳定排序，那么第一次排序的结果会被保留；如果第二次排序不稳定，同价格商品的销量顺序就乱套了。

所以当你听到“某某排序算法是稳定的”这句话，要立刻联想到这种“多级排序”场景。写代码时如果对排序稳定性没有把握，稳妥的办法是用稳定排序，或者给元素加上序号做第二关键字，自己构造稳定性。我在某个模拟项目中就是这么干的：给每条记录加一个自增序号，排序时以业务字段为主、序号为辅，这样不管底层算法稳不稳定，最终结果看起来都是稳定的。

5.3 常数项：为什么同复杂度算法实测差距巨大

复杂度分析把系数和低阶项都丢掉了，这在实际对比中会误导人。同样 O(n log n) 的排序算法，快排的常数项可能是堆排序的 1/3 甚至更小。为什么？快排的主要操作是移动和比较相邻或较近位置的元素，对缓存友好；堆排序则是反复执行堆顶和堆底的远距离交换，对缓存不友好；归并排序虽然也很规整，但多了一次辅助数组的写入和拷贝。

用生活类比解释：两个人都要搬家，距离一样，复杂度一样；但一个人开小货车一次装得满满当当，另一个人骑小电驴一箱一箱搬，就是常数的差距。这就是为什么“理论最优”和“工程最优”经常不是同一个东西。

5.4 工程库里的混合排序：印象中总是快排，其实是多算法组合

如果你去翻某个主流语言运行时里的排序实现，会发现它并不是单一算法，而是复合策略。大体逻辑可以概括为：

• 大规模数据：快排（划分排序）。
• 递归到规模小于某个阈值（比如几十个元素）：切到插入排序。
• 检测到递归深度超过阈值：切到堆排序，防止最坏退化。
• 如果能天然识别出“数据里已经存在连续有序片段”，则可能走类似 Timsort 的归并逻辑。

这套策略背后的复杂度分析是动态的：复杂度分析不只告诉你“哪个算法平均最优”，还告诉你“哪个算法在最坏情况下有兜底”“哪个算法在小数据下常数最小”。我觉得这才是复杂度分析真正值钱的地方：它是设计混合策略的决策依据，而不是期末卷面上的一行结论。

6. 从分析到选型：排序算法实战中的判断框架

6.1 按数据规模与特征选型

面对一个排序需求，不要一上来就写快排。先问自己四个问题：

1. 数据量多大？
2. 数据是不是基本有序？
3. 稳定排序是否必须？
4. 额外内存是否有限制？

回答完这四个问题，选型框架就很清晰了：

场景	推荐做法	理由
数据量很小（百量级）	插入排序	常数小，稳定
数据量大、不要求稳定	库自带排序（通常是快排系）	性能均衡
数据量大、要求稳定	归并排序系	稳定且 O(n log n)
内存极受限、必须有界最坏时间	堆排序	O(1) 空间，没有退化风险
数据基本有序	插入排序或识别有序片段的归并	能利用已有有序性

6.2 一次真实性能排查：复杂度不是首要瓶颈

之前接过一个“排序很慢”的排查。一开始大家都在讨论快排和堆排哪个好，结果我把日志拉出来一看，问题根本不在排序算法本身：排序前每次比较都触发了一次隐藏的字符串解析，而那个解析会扫一大段报文。比较成本从纳秒级变成了微秒级，O(n log n) 的排序被放大了上千倍。

这个经历给我的启发是：复杂度分析建立在“比较操作代价可忽略”的假设上，但真实系统里，如果比较函数昂贵，排序总成本的公式会变成“比较次数 × 单次比较代价 + 移动次数 × 移动代价”。这时候你要优化的不是换算法，而是减少比较次数，或者缓存比较结果。所以做性能分析时，先确认瓶颈在“比较/移动”还是“算法选择”，不要一上来就重构排序。

6.3 想验证自己的理解，可以做三个小实验

如果看完这些分析手痒，我建议你亲手跑三个小实验，很快就能看到复杂度分析在真实数据上是如何体现的：

实验一：分别用插入排序和快速排序排 10 万元素，记录耗时。你会发现快排快得不是一点半点，这就是 O(n log n) 对比 O(n²) 的真实差距。

实验二：把快排改成固定取最左元素为枢轴，然后对一个已经排序好的 10 万元素数组排序，观察耗时是否爆炸。再改成随机枢轴对比，你会深刻理解“最坏情况”不是一个吓唬人的词。

实验三：构造 100 万个元素，先用归并排序，再用堆排序，比较内存峰值和时间。这个实验能让你直观感受到空间复杂度和常数项的影响。

我个人始终觉得，排序算法是少数“复杂度分析能清清楚楚落到实测数据上”的主题。你把这几个实验做下来，比看十遍教程都管用。以后遇到任何自称 O(n log n) 的排序，你也敢底气得问一句：你的最坏情况是多少？常数项如何？缓存友好吗？稳定吗？——把这些问题过一遍，才是真正把复杂度分析学进了脑子里。