为什么不同 sorting algorithms 的运行速度和适用场景存在差异？

2026-11-04技术老齐

没有一种排序算法适合所有场景。选择时，先确认稳定性、内存和最坏耗时等限制，再根据数据规模、已有顺序和键值类型比较速度。普通业务代码通常应优先使用语言或标准库提供的排序函数。

平均速度稍慢的算法，也可能更适合当前任务：它可能占用更少的内存，保留相同键值记录的原有顺序，或对最坏情况下的耗时有保证。

为什么运行速度会不同？

算法执行的操作数量不同

设待排序元素数量为 (n)：

插入排序在随机输入上的平均时间复杂度为 (O(n^2))。
归并排序、堆排序的最坏时间复杂度为 (O(n \log n))。
快速排序的平均时间复杂度为 (O(n \log n))，但最坏可能达到 (O(n^2))。

数据量越大，这些增长速度的差异就越明显。不过，复杂度描述的是增长趋势，不能直接换算成运行秒数。

比较和移动元素的成本不同

比较两个整数通常成本很低，比较长字符串却可能需要检查许多个字符。如果排序键的计算很复杂，提取键值就可能花掉大部分时间。

移动数据也有成本。交换大型记录、交换对象引用和把数据写回磁盘，成本各不相同。因此，比较次数少的算法，实际运行未必更快。

算法对输入顺序的利用程度不同

插入排序处理已经有序的数据时，只需线性扫描，时间复杂度为 (O(n))。数据接近有序、逆序对较少时，它也能减少元素移动。

某些自适应排序算法会识别已有的有序片段。即使元素数量相同，完全随机、接近有序或包含大量重复值的输入，排序耗时也可能相差很大。

实现和硬件也会影响结果

连续访问数组通常有利于利用 CPU 缓存，频繁跳跃访问则可能增加缓存失效。递归、内存分配、分支预测，以及代码采用解释执行还是本地编译，都会影响实际速度。

即使两个算法的时间复杂度都是 (O(n \log n))，实际耗时也可能不同。处理小数组时，初始化和函数调用等固定开销，甚至可能抵消复杂度较低带来的收益。

常见排序算法如何比较？

下表以常见实现为准。额外空间不包含输入数据本身，但包含递归栈。

算法	时间复杂度	额外空间	稳定性	适用情况
插入排序	最好 (O(n))，平均及最坏 (O(n^2))	(O(1))	可稳定	数据量小，或数据接近有序
选择排序	最好、平均及最坏均为 (O(n^2))	(O(1))	通常不稳定	需要限制交换次数，且能接受大量比较
快速排序	平均 (O(n \log n))，最坏 (O(n^2))	常见递归实现平均 (O(\log n))，最坏 (O(n))	通常不稳定	内存中的数组排序，重视平均性能
归并排序	常见实现为 (O(n \log n))	数组实现通常为 (O(n))	可稳定	需要稳定排序，或适合顺序归并的数据
堆排序	平均及最坏 (O(n \log n))	迭代实现为 (O(1))	通常不稳定	额外内存有限，并要求最坏时间保证
计数排序	(O(n+k))，(k) 为键值范围大小	稳定输出的常见实现为 (O(n+k))	可稳定	键为整数，且取值范围较小

“可稳定”表示需要在实现中正确处理相等键值。例如，归并排序合并两个有序段时，遇到相等键值应优先取左段元素，才能保留原有顺序。

稳定性是指排序键相等的记录在排序后保持原有的相对顺序。比如，订单原本按提交时间排列，再按金额做稳定排序，同金额的订单就仍按提交时间排列。如果排的是没有附加信息的整数，通常不需要考虑稳定性。

选择排序的比较次数多，但交换次数为 (O(n))。写入成本远高于比较成本时，这个特点可能有用，是否值得采用还要看具体的存储方式。

计数排序利用了整数键的范围限制。如果元素很少，键值范围却很大，为整个范围分配计数数组就很不划算。

如何根据具体问题选择？

1. 先确定需要什么结果

很多任务不需要完整排序，减少不必要的工作往往比更换排序算法更有效：

只要最小值或最大值，一次扫描即可，时间为 (O(n))。
只要前 (k) 小的元素，且 (k \ll n)，可以考虑维护大小为 (k) 的堆，通常需要 (O(n \log k)) 时间。
只要中位数或第 (k) 小的值，可以考虑选择算法。Quickselect 的期望时间为 (O(n))，基本实现最坏为 (O(n^2))。

2. 写清楚必须满足的限制

先确认以下条件：

相同键值的记录是否必须保持原有顺序？
能否分配与输入规模成正比的额外内存？
是否要求最坏情况下仍有明确的时间上界？
数据能否全部放进内存？
键值是否有可利用的限制，例如较小的整数范围？

如果数据放不进内存，磁盘读写会成为主要成本。常见做法是分块读取，在内存中分别排序，再归并这些有序块，这就是外部归并排序。

3. 根据数据特征缩小候选范围

数据量小或接近有序时，可以考虑插入排序。需要稳定性时，可以选择稳定归并或标准库中的稳定排序。如果额外内存有限，又要求最坏时间上界，可以考虑堆排序。

一般应用优先使用标准库更省事。成熟的排序实现可能组合多种策略，例如对小分区使用插入排序，或在出现退化迹象时切换算法。具体行为应以所用库的文档为准。

4. 用实际数据测试

性能测试至少应覆盖随机、已排序、逆序和大量重复键的数据，并使用业务中真实的数据规模与记录类型。

每次测试都要使用内容相同、彼此独立的输入。如果排序会修改原数组，反复排序同一个数组，就会让后续测试变成对已有序数据的排序。

还要明确耗时是否包含复制数据、计算排序键、内存分配和磁盘读写。测试排序本身与测试完整业务流程，回答的是不同问题。

代码示例：稳定排序与只取前几项

Python 可以分别处理完整排序和只取前几项的需求，无须依赖具体排序算法的实现细节。

from heapq import nsmallest

orders = [
    {"id": "A", "amount": 80},
    {"id": "B", "amount": 30},
    {"id": "C", "amount": 80},
    {"id": "D", "amount": 10},
]

# 完整排序：按金额升序，返回新列表。
# sorted() 保证稳定性，因此金额相同的 A 仍排在 C 前面。
ordered = sorted(orders, key=lambda order: order["amount"])
print([order["id"] for order in ordered])
# ['D', 'B', 'A', 'C']

# 只需要金额最小的两条记录。
cheapest = nsmallest(2, orders, key=lambda order: order["amount"])
print([order["id"] for order in cheapest])
# ['D', 'B']

sorted() 返回新列表，list.sort() 修改原列表。这里使用 sorted() 是为了保留原始输入。如果需要先按金额、再按编号排序，可以使用组合键：

ordered = sorted(
    orders,
    key=lambda order: (order["amount"], order["id"]),
)

组合键规定了金额相同时按什么次序排列；稳定性保留的是排序键相同的记录在输入中的顺序，两者用途不同。

比较时容易忽略什么？

时间复杂度的结论有适用前提。基于比较、处理任意输入的排序，在最坏情况下需要 (\Omega(n \log n)) 次比较。计数排序和基数排序利用键值结构，因此不受这个比较模型下界的限制。

平均时间不能代替最坏情况的保证。随机选取枢轴可以降低快速排序持续产生极端不均衡分区的概率，但普通随机化快速排序仍存在 (O(n^2)) 的最坏情况。

“原地排序”仍可能使用额外内存。快速排序即使在原数组中交换元素，递归栈也会占用空间。

比较函数必须提供一致的排序关系。如果比较结果前后矛盾，算法就无法可靠地满足排序要求。遇到缺失值、NaN 或混合类型时，应先明确它们的排序规则，再讨论性能。