排序算法四十年：从 Bubble 到 Timsort，谁在决定你电脑的快慢

如果你问一个程序员"计算机里被调用最多的算法是什么"，答案很可能是排序。数据库建索引、搜索引擎排序结果、操作系统调度、乃至你手机相册按时间排列照片，背后都是排序。它看似基础，却藏着算法工程最迷人的取舍。

朴素时代（1950s–1960s）。最早的计算机程序里，冒泡、插入、选择这类 O(n²) 排序是主流——它们好写、好懂，但面对稍大的数据就力不从心。真正的转折发生在 1960 年，Tony Hoare 在莫斯科访问时为了给俄文句子排序，灵光一现写出了快速排序（详见今日第②篇）；几乎同时，归并排序的思想（源自 von Neumann 1945 年的归并思想）被系统化，第一次把排序压到了 O(n log n)。

理论成熟期（1970s–1990s）。随着 CLRS《算法导论》等教材把排序讲成严密体系，人们认识到：基于比较的排序不可能快于 Ω(n log n)（今天的第③篇会证明）。于是竞争转向"常数因子"与"最坏情况"——堆排序原地 O(n log n) 但缓存不友好；快排平均最快却可能退化为 O(n²)。1997 年，David Musser 提出 introsort：正常用快排，一旦递归过深就切换到堆排序，彻底避开最坏情况，它至今是 C++ std::sort 的底层。

自适应时代（2000s–至今）。2002 年 Python 核心开发者 Tim Peters 设计了 Timsort：它利用真实数据中大量存在的"已有序片段（run）"，把归并与二分插入结合，做到最好 O(n)、最坏 O(n log n) 且稳定。今天 Python 的 sorted()、Java 对象数组排序、Android 底层都在用它。这场演进的教训是：没有"最好"的排序，只有"最贴合数据分布"的排序。

而我们今天学的插入/选择/冒泡，并不是被淘汰的化石——恰恰相反，它们的小常数与原地性，正是 Timsort、introsort 在"小数组收尾"时回退使用的子程序。理解它们，才能理解现代排序为何这样设计。

图：排序算法四十年演进脉络

参考代码（Python）

下面用计时直观感受：小数组上简单排序未必更慢。

import time, random
def insertion_sort(a):
    for i in range(1, len(a)):
        key=a[i]; j=i-1
        while j>=0 and a[j]>key:
            a[j+1]=a[j]; j-=1
        a[j+1]=key
    return a

a=[random.randint(0,1000) for _ in range(20)]
t1=time.perf_counter(); insertion_sort(a.copy()); t1=time.perf_counter()-t1
t2=time.perf_counter(); sorted(a); t2=time.perf_counter()-t2
print(f"n=20 插入排序 {t1:.6f}s vs 内置 {t2:.6f}s")

关联推荐

• 从冒泡到快排：排序算法怎样悄悄决定你电脑的快慢 — 一篇从工程视角讲排序性能的姊妹文
• 算法与问题求解入门：为什么它是计算机科学的灵魂 — 理解"为什么同样的任务不同算法快慢天差地别"
• 算法通关训练营·入门篇 — 系统补齐算法基础，衔接排序轨道