排序算法不只是面试题。它们集中展示了时间复杂度、空间换时间、稳定性以及输入特征如何影响程序性能。冒泡排序、插入排序、归并排序、快速排序和 Timsort 的差别，也不能只用一个 Big O 符号概括。
五种算法到底在做什么
| 算法 | 最好时间 | 平均时间 | 最坏时间 | 额外空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 通常稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | 取决于实现 | 通常不稳定 |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | 稳定 |
这里的“最好情况”依赖具体实现。例如，冒泡排序只有在加入“本轮是否发生交换”的检测后，才能对已排序输入达到 O(n)。快速排序则高度依赖枢轴选择：持续选中极端值可能产生严重不平衡的分区，使时间复杂度退化为 O(n²)。
这几种算法的核心策略可以概括为：
- 冒泡排序反复比较相邻元素，把较大的元素逐步推向末尾。
- 插入排序维护一个已排序区间，将新元素插入合适位置。
- 归并排序拆分序列，再线性合并已经排好序的子序列。
- 快速排序围绕枢轴分区，再递归处理两侧。
- Timsort利用现实数据中已有的有序片段，并结合插入排序与归并策略。
Big O 相同，不代表实际表现相同
归并排序、快速排序和 Timsort 的典型复杂度都可以出现 O(n log n)，但它们的工程表现并不等价。
归并排序的最坏时间仍是 O(n log n)，性能容易预测，代价是通常需要 O(n) 辅助空间。快速排序往往具有良好的局部性，但朴素实现可能退化，而且递归深度也需要控制。Timsort 会识别输入中已经递增或递减的连续片段，因此面对部分有序的数据时尤其有效。
稳定性同样会改变结果。稳定排序会保留“键相同元素”的原始相对顺序。假设员工记录已经按入职时间排列，再按部门执行稳定排序，同一部门内的员工仍会保持原有的入职时间次序。Python 的 list.sort() 和 sorted() 都是稳定排序。
可运行实验：比较结果、稳定性与耗时
下面的程序实现了冒泡排序、插入排序、归并排序和一个教学用途的快速排序，并把它们与 Python 内置的 Timsort 进行比较。将代码保存为 sorting_demo.py 后运行 python sorting_demo.py 即可。
from __future__ import annotations
from random import Random
from time import perf_counter
from typing import Callable, TypeVar
T = TypeVar("T")
def bubble_sort(values: list[T]) -> list[T]:
result = values.copy()
for end in range(len(result) - 1, 0, -1):
swapped = False
for i in range(end):
if result[i] > result[i + 1]:
result[i], result[i + 1] = result[i + 1], result[i]
swapped = True
if not swapped:
break
return result
def insertion_sort(values: list[T]) -> list[T]:
result = values.copy()
for i in range(1, len(result)):
current = result[i]
j = i - 1
while j >= 0 and result[j] > current:
result[j + 1] = result[j]
j -= 1
result[j + 1] = current
return result
def merge_sort(values: list[T]) -> list[T]:
if len(values) <= 1:
return values.copy()
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
merged: list[T] = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
return merged + left[i:] + right[j:]
def quicksort(values: list[T]) -> list[T]:
if len(values) <= 1:
return values.copy()
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
higher = [value for value in values if value > pivot]
return quicksort(lower) + equal + quicksort(higher)
def benchmark(name: str, algorithm: Callable[[list[int]], list[int]], data: list[int]) -> None:
start = perf_counter()
result = algorithm(data)
elapsed_ms = (perf_counter() - start) * 1000
assert result == sorted(data)
print(f"{name:14} {elapsed_ms:9.3f} ms")
def main() -> None:
rng = Random(42)
data = [rng.randrange(100_000) for _ in range(3_000)]
algorithms = {
"bubble": bubble_sort,
"insertion": insertion_sort,
"merge": merge_sort,
"quicksort": quicksort,
"built-in": sorted,
}
for name, algorithm in algorithms.items():
benchmark(name, algorithm, data)
employees = [
{"name": "Chen", "department": "Platform"},
{"name": "Li", "department": "Data"},
{"name": "Wang", "department": "Platform"},
]
print(sorted(employees, key=lambda item: item["department"]))
if __name__ == "__main__":
main()
这段代码适合观察趋势，但不是严谨的科学基准。进程调度、Python 解释器开销、数据规模和输入分布都会影响结果。进行正式测量时，可以使用标准库 timeit 或 python -m timeit，并重复运行多次。
教学版 quicksort() 还创建了三个新列表，因此不能把它的内存表现等同于原地快速排序。它的意义是清楚展示“分区并递归”的结构，而不是替代生产环境中的 sorted()。
用问题检查自己是否真的理解
阅读代码后，可以尝试回答这些问题：
- 为什么带提前退出判断的冒泡排序能在已排序输入上达到 O(n)？
- 为什么插入排序虽然最坏为 O(n²)，却仍适合处理很短或接近有序的序列？
- 归并排序为什么能保证 O(n log n)，又为什么通常需要额外空间？
- 什么样的枢轴选择会使快速排序退化为 O(n²)？
- 当记录具有相同排序键时，稳定排序保留的是什么信息？
- 为什么不能仅根据平均时间复杂度断定快速排序一定优于 Timsort？
还可以把示例中的 data 分别替换为 list(range(3000))、逆序列表和包含大量重复值的列表，观察不同算法如何响应输入结构。
实际项目中的选择
在 Python 业务代码中，默认选择通常应是 sorted(iterable, key=...) 或 list.sort(key=...)。前者返回新列表，后者原地修改现有列表；两者都使用稳定的 Timsort，并经过成熟优化。
只有在学习算法、满足特殊内存约束、实现底层库，或者需要针对特定数据结构优化时，才值得自行实现排序。做决定时检查四件事：输入规模、数据是否部分有序、是否要求稳定、是否允许分配额外内存。Big O 是重要的起点，但真正的工程选择还要结合常数开销、数据分布和实现质量。