> ## Content Index
> Fetch the complete content index at: https://huizhou92.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# 为了翻译俄语，他发明了世界上最流行的排序算法
- URL: https://huizhou92.com/quicksort-tony-hoare-moscow-translation/
- Published: 2026-11-22T11:37:08.000Z
- Updated: 2026-11-22T11:37:08.000Z
- Description: 1959 年莫斯科的磁带词典、1960 年伦敦的六便士赌局，与 ALGOL 60 如何用一行递归解放了快速排序
- Author: huizhou92
- Tags: #lang-zh-cn, IT-Chronicles, Quicksort, Tony-Hoare, ALGOL-60, algorithms, Turing-Award, Elliott-803

> 1959 年莫斯科的磁带词典、1960 年伦敦的六便士赌局，与 ALGOL 60 如何用一行递归解放了快速排序

![1950 至 1960 年代典型的磁带存储机柜（IBM 729 磁带机）](https://upload.wikimedia.org/wikipedia/commons/thumb/3/3c/IBM_729_tape_drives.agr.jpg/1280px-IBM_729_tape_drives.agr.jpg)

1959 年秋，25 岁的牛津毕业生 Tony Hoare 来到莫斯科国立大学，在数学家 Andrey Kolmogorov 所在的院系做访问研究生。他的研究方向是用计算机将俄语新闻自动翻译成英语。

当年的计算机内存极其狭小，装不下整本俄英双语词典，只能按字母顺序录在一卷长长的**磁带**上。

磁带是一种顺序存储介质，其磁头无法随机跳转。如果照着俄语句子里的词序逐个查词，假设第一个词以 S 开头、第二个词以 B 开头，磁带机就得急刹倒带。就这样来回的倒带，翻译短短一句二十个词，就足以把整台大型机拖垮。

为了解决这个问题，Hoare 首先想到的是把查词顺序彻底反过来。他决定先在内存里把一整句俄语单词**按字母顺序排好**，记下每个词在原句中的位置，再让磁带机从 A 到 Z 顺序扫一遍，一次性取出所有释义，最后按原位置拼回句子。

为了省下倒磁带的时间，他必须先在内存里解决一个前置问题，怎样把这堆单词排得足够快。

### 没有递归

Hoare 最先想到的是冒泡排序，两两比较相邻单词，逆序就互换。但他在草稿纸上稍微演算一下就知道这个方法行不通: 比较次数会随词数按平方级暴涨，文本一长，内存排序消耗的时间甚至会超过直接倒磁带。

他换了一种切分思路。从词堆里随便挑一个词作为**基准值（Pivot）**，派两个指针从数组最左端和最右端向中间扫描。左边遇大停下，右边遇小停下，两者就地互换，继续向中间夹逼。

两个指针碰头时，整堆单词就被原地切成了两半，左边全比基准值靠前，右边全比基准值靠后，不需要额外开辟一倍内存。接下来只要对左右两半重复完全相同的切分，直到每段只剩一个词，排序就自然完成了。

这套分治直觉在数学证明上完美无缺，可当 Hoare 试图把它写成代码时，却一头撞上了编程语言的天花板。1959 年，他唯一掌握的编程语言是在牛津学过的 Mercury Autocode。那时的语言还没有**递归**，硬件也没有现成的调用栈。

没有递归，就意味着“对左右两半重复同样的事”这句话根本写不出来。切完第一刀后，他只能自己在内存里开辟数组充当待办清单，手动压入右半边的起止下标，跳转处理左半边，再小心翼翼地维护清单指针，防止溢出。

原本在草稿纸上极其优雅的想法，落地下来的代码变成了一团充斥着下标与跳转指令的乱麻。Hoare 写得极痛苦，甚至没法用 Mercury Autocode 向别人讲清这个算法到底怎么运转。

带着这个在纸上想通、在机器里却卡壳的半成品，他结束了莫斯科的访学。

![1960 年英国计算机厂商 Elliott Brothers 制造的 Elliott 803 计算机实物](https://upload.wikimedia.org/wikipedia/commons/thumb/1/14/Elliott_803.jpg/1280px-Elliott_803.jpg)

*英国计算机厂商 Elliott Brothers 推出的 Elliott 803 计算机实物。1960 年 8 月 Tony Hoare 入职该公司后，正是用这台机器的机器码硬敲出快速排序，跑赢了当时的明星算法 Shellsort。Photo by Steve Elliott, CC BY-SA 2.0, via Wikimedia Commons.*

### 伦敦的六便士赌局与 Elliott 803

离开莫斯科前，Hoare 在当地一场英国科学仪器展上兼职担任俄语翻译，意外结识了英国计算机厂商 **Elliott Brothers** 的代表，并拿到了一份程序员录用通知。

1960 年 8 月，他回到伦敦入职。巧合的是，上司兼导师 Pat Shackleton 布置的第一项练手任务，正是他憋了一年的老问题，为公司主力机型 Elliott 803 编写内存排序子程序。Shackleton 指定采用美国工程师 Donald Shell 前一年刚刚发表、号称当时最快的 **Shellsort（希尔排序）**。

Hoare 很快用机器码写完了 Shellsort。交差时，他按捺不住心里压了一年的念头，怯生生地向老板提了一句，自己在莫斯科想过一种通常更快的排序方法。

Shackleton 压根不信刚入行的新人随手想出来的土办法，能赢过刚刚轰动学界的希尔排序。他当场掏出**六便士（Sixpence）** 和 Hoare 打赌，赌这个年轻人拿不出更快的排序程序。

![1960 年代初英国流通的伊丽莎白二世时期旧六便士硬币](https://upload.wikimedia.org/wikipedia/commons/thumb/0/06/British_sixpence_1962_reverse.png/1280px-British_sixpence_1962_reverse.png)

*1960 年代初英国流通的伊丽莎白二世时期旧六便士硬币。Pat Shackleton 当初正是用这样一枚硬币与刚入职的 Tony Hoare 打赌，最终在实测结果面前愿赌服输。Scan by Retroplum, Public Domain, via Wikimedia Commons.*

为了赢下这枚硬币，Hoare 只能硬着头皮重新面对莫斯科遗留的难题。Elliott 803 同样没有递归，他必须直接用赤裸的机器码手工维护那张子区间上下界栈。为了防止手写栈爆掉，他刻意定下规矩：每次切完区间后，总是先把较长的一半压栈，优先处理较短的一半，借此把栈深死死锁在对数级别。

![Hoare 在 Elliott 803 上“先压长半边、先算短半边”的手写栈防溢出原理动态演示](quicksort-manual-stack.gif)

*技术动态示意图（Illustration）：面对极端偏斜的切分，若先压短半边、先处理长半边，手写栈会按 $O(n)$ 线性暴涨直至溢出；而按 Hoare 定下的规矩“先压长半边、立刻处理短半边”，每次活跃区间至少减半，手写栈最大深度被死死锁在 $\\log\_2 n$ 以内。*

最终，Hoare赢得了这场赌局，可他心里的尴尬依然没解开。那段用 Elliott 803 机器码拼出来的排序程序实在过于晦涩，外人根本读不懂。如果一个算法只能以这种面目存在，它大概率只会老死在一家英国小厂的内部磁带库里。算法已经跑通了，配得上它的编程语言却还没到。

### 递归

转机在半年后悄然到来。1961 年复活节前后，Hoare 随同事前往英国海滨城市布莱顿，参加一门关于全新编程语言 **ALGOL 60** 的短期培训课，讲台上站着 Peter Naur、Edsger Dijkstra 与 Peter Landin。

就在这间教室里，困扰了他整整一年半的死结突然松动了。Hoare 第一次听说，ALGOL 60 的过程原生支持**递归**，允许一个过程在执行过程中途直接调用自己。程序员不再需要手动开辟数组来记账，编译器运行时会在底层自动压栈、保存边界现场，并在返回时恢复。

他立刻拿起笔，用 ALGOL 60 重写了那个排序算法。原本在 Elliott 803 机器码里几十上百行战战兢兢维护的手工栈，在原生递归面前瞬间坍缩成了十几行高度对称的代码。先调用 `partition` 把当前区间切开，再让 `quicksort` 直接调用自己处理左半边和右半边。

算法的数学骨架第一次毫无遮挡地显露在纸面上。1961 年 7 月，这两段极简代码正式发表在《美国计算机学会通讯》（Communications of the ACM）上，编号为 **Algorithm 63（`partition`）与 Algorithm 64（`quicksort`）**。从 1959 年莫斯科草稿纸算起，快速排序等了一年多，终于有了能被全世界读懂的表达形式。

![图灵奖得主、快速排序发明人 Sir Tony Hoare 肖像](https://upload.wikimedia.org/wikipedia/commons/thumb/9/97/Sir_Tony_Hoare_IMG_5121.jpg/1280px-Sir_Tony_Hoare_IMG_5121.jpg)

*快速排序发明人、1980 年图灵奖得主 Sir C. A. R. (Tony) Hoare。除了快速排序，他还提出了霍尔逻辑与通信顺序进程（CSP），后者直接启发了 Go 语言的并发模型。Photo by Rama, CC BY-SA 2.0 fr, via Wikimedia Commons.*

### 六十五年后的物理巧合与“简洁”的边界

短短十几行 ALGOL 60 代码让快速排序迅速走进了各国计算机教材与工业标准库。可一旦投入真实生产环境，工程界很快撞上了它最危险的软肋。

快速排序的平均复杂度是极佳的 $O(n \\log n)$，但如果待排序数组本来就有序，而程序又固定挑首元素当基准值，每次切分只能削掉一个元素，耗时就会瞬间退化到与冒泡排序无异的 $O(n^2)$。

归并排序和堆排序在最坏情况下都能稳稳守住 $O(n \\log n)$。奇怪的是，从 C 语言 `qsort`、C++ `std::sort` 到 Rust 不稳定排序，工业界宁可给快排打满补丁（三数取中选基准、小数组切插入排序，以及 1997 年 David Musser 提出在递归过深时切回堆排序兜底的 **Introsort**），也始终不肯换掉它。

答案兜兜转转，最终又绕回了物理硬件。

1959 年，Hoare 因为大型机内存匮乏，刻意把快排设计成了**原地排序（In-place）**，只靠双指针在连续内存里相向扫描、就地交换，省去了归并排序成倍的辅助内存与数据拷贝。

六十五年后，现代 CPU 算力早已把主存甩开两个数量级，决定程序快慢的胜负手变成了 **L1 与 L2 缓存命中率**。堆排序虽然也是原地排序，但它在树形节点间频繁跨步跳跃，极易打穿缓存行；反观 Hoare 当年为省内存画出的双向顺序扫描，恰好沿着连续地址线性推进，完美吃满了现代处理器的缓存预取红利。

1980 年，Hoare 站上 ACM 图灵奖领奖台发表演讲《皇帝的旧衣》，如实回顾了莫斯科磁带、伦敦六便士与布莱顿 ALGOL 60 课堂，并在尾声留下一句软件工程界流传至今的箴言。

> "I conclude that there are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult."  
>  
> （设计软件有两种方式，一种是把它做得极其简单，简单到明显没有缺陷；另一种是把它做得极其复杂，复杂到看不出明显的缺陷。第一种方式要困难得多。）

1959 年那卷磁带逼出了快速排序雏形，1960 年六便士证明了它的速度，而 1961 年 ALGOL 60 一行递归，最终让它褪去晦涩汇编外壳，站到了“明显没有缺陷”那一边。