Tony Hoare 与快速排序：一个在电梯里想出来的算法，拿下图灵奖

1960 年，年轻的英国数学家 Tony Hoare 在莫斯科国立大学做访问学者，参与一台机器翻译设备的开发。他需要把俄文单词按字典序排好，却嫌当时的排序方法太慢。据他本人回忆，灵感来得意外——在一次等待电梯（也有说是坐火车）的时候，他想到了一个"分而治之"的办法：选一个基准值，把比它小的放左边、比它大的放右边，再对两边递归。这就是快速排序。

这个想法在 1961 年正式发表，迅速成为算法史上的里程碑。它的美妙在于平均只需 O(n log n)，且常数因子极小——在实践中常常比同时代的归并排序还快。代价是：如果每次都选到最坏基准（比如已排序数组选到端点），会退化到 O(n²)。这催生了"随机化快排""三数取中"等工程改良，也引出今天第③篇要讲的比较排序下界。

Hoare 的贡献远不止快排。他还提出了形式化方法（用数理逻辑证明程序正确性）、CSP 并发模型（影响了 Go 语言的 channel 设计），并因这些奠基性工作获得 1980 年图灵奖——计算机界的诺贝尔奖。他有一句名言："构建软件设计有两种方式：一种简单到没有明显缺陷，另一种复杂到没有明显缺陷。前者要难得多。"

今天，快排的变种仍运行在无数设备的标准库里。一个在异国他乡等电梯时冒出的念头，就这样静静支撑了此后六十年的计算世界。明天我们会在 B3 节点系统拆解快排的分治与分区。

图：以 6 为基准的一次分区过程

参考代码（Python）

快排的"分治+分区"思想，下面给出最易读的列表版实现。

def quicksort(a):
    if len(a)  pivot]
    return quicksort(left) + mid + quicksort(right)

关联推荐

• 从冒泡到快排：排序算法怎样悄悄决定你电脑的快慢 — 从冒泡一路讲到快排的宏观脉络
• P vs NP：算法世界里那道"世纪难题" — 理解算法问题的难度边界
• 算法与问题求解入门 — 从"什么是算法"建立整体认知