排序与图灵奖：那些改变世界的算法思想，如何穿越六十年

图灵奖是计算机界的最高荣誉。许多人不知道，排序这个"基础"问题中，埋着多位图灵奖得主的思想种子。把它们的"先驱思考"与"后世印证"连起来看，会比单独学算法更受启发。

先驱：Tony Hoare（1980 图灵奖）。1960 年写下快排时，Hoare 想解决的只是"把俄文句子排好序"的小事。但快排体现的分治 + 随机化思想，后来渗透进无数算法。今天它运行在几乎每台设备的标准库里——一个工程小工具，印证了"好思想会自己长腿走路"。

先驱：Robert Tarjan（1986 图灵奖）。他奠定的不相交集合（并查集）与强连通分量算法，是图论与排序相关结构（如 Kruskal 最小生成树、外部归并）的底层支撑。我们今天排序海量数据用的"多路归并""外部排序"，离不开他建立的数据结构理论。

先驱：Stephen Cook（1982 图灵奖）。他提出的 NP-completeness 理论，为"问题的难度边界"立下了标尺——而排序的 Ω(n log n) 下界（今日第③篇），正是这种"难度量化"思维在基础问题上的最早、最干净的范例之一。

后世印证：这些 1960–1980 年代的思想，今天不仅没过时，反而被深度学习、分布式系统重新激活——分布式排序（如 MapReduce 的 shuffle）、GPU 排序、数据库查询优化，全是当年理论的工业回响。排序告诉我们：真正的算法思想不随时间折旧，只会随着算力扩张被用得更广。

关联推荐

• P vs NP：算法世界里那道"世纪难题" — 顺着 Cook 的 NP 完备理论继续深入
• 图灵奖里的算法：那些真正改变世界的获奖工作 — 更完整的图灵奖算法图谱
• 算法与问题求解入门 — 从总入口进入算法通关轨道