快排算法之父、图灵奖得主托尼 · 霍尔（Tony Hoare）去世了，享年 92 岁。

凡是学过计算机的人，几乎没有谁能绕开快速排序（Quicksort）。

它是世界上使用最广泛的排序算法之一，被写进了几乎所有主流编程语言的标准库，从 C 到 Java 到 Python，随处可见它的身影。

快速排序只是他漫长学术生涯的起点。

他是 1980 年图灵奖得主，提出了用数学方式证明程序正确性的霍尔逻辑，还创造了直接影响 Go 语言设计的 CSP 并发模型。

他还亲手制造了后来被他自己称为 " 十亿美元的错误 " 的空引用（Null Reference），深刻影响了后世的 Java、C++ 等语言。

在莫斯科 " 排 " 出来的算法

快速排序的故事要从 1959 年说起。

那一年，25 岁的霍尔还是个访问学生，在莫斯科国立大学学习机器翻译。

他参与的项目需要把俄语句子中的单词排好序，然后去一卷磁带上存储的俄英词典里查找对应的英文。

排序是第一步，霍尔在沙发上最先想到的是冒泡排序。

冒泡排序的原理很简单：

给定一个需要排序的元素列表，首先比较前两个元素，如果顺序错误则交换它们。然后比较列表中的第 2 个和第 3 个元素，如果顺序错误则交换它们。

以此类推，直到遍历完整个列表，如果在此过程中无需交换任何元素，则说明列表已经排序正确，此时停止。

但很快，他就发现这个方法太慢了，时间复杂度是 O ( n ² ) ，处理上规模的数据根本不够用。

于是他开始琢磨一种全新的思路：

先从数组里选一个元素当 " 基准 "，然后把比它小的全部挪到左边，比它大的全部挪到右边，接着对左右两部分各自重复这个过程。

也就是 " 分而治之 "，把一个大问题拆成小问题，递归解决。

回到英国后，他的同事对此表示怀疑，掏出六便士跟他打赌，不信他能找到比当时流行的希尔排序（Shellsort）更快的算法。

希尔排序是插入排序的升级版。最简单的插入排序就像整理扑克牌一样，逐个把牌插入到前面已经排好序的对应位置。

但在计算机算法中，如果数组里的元素 " 离自己该在的位置很远 "，每个元素都要一步一步往前挪，效率极低。

希尔排序的做法是先粗略分组整理，再精细微调。设置一个步长把数组分成多个子数组，对每个子数组做插入排序；然后逐步缩小步长，直到步长为 1。

希尔排序的时间复杂度最坏情况为 O ( n ² ) ，最好情况为 O ( n log n ) ，平均情况在 O ( n log n ) 到 O ( n ² ) 之间。

霍尔用了一个下午的时间完善了快速排序的细节，赢下了这场赌局。

事实证明，快速排序的平均时间复杂度 O ( n log n ) ，只在极少情况下比希尔排序慢。

并且由于快速排序是原地排序，只需要 O ( log n ) 的辅助空间，不像归并排序那样需要额外开辟一整块 O ( n ) 的内存。

再加上它对现代计算机缓存机制格外友好，实际运行速度往往比同等复杂度的其他算法更快。

缓存的设计遵循时间局部性和空间局部性。访问一个数据时，它附近的连续数据大概率也会被访问。近期访问过的数据，大概率会被再次访问。

快速排序完美契合这两个特性，就像整理一摞连续摆放的文件，手边（缓存）一次放 10 份，不用来回跑。

从 1960 年代至今，快速排序已经成为计算机科学教育中绕不开的内容，也是无数软件和数据库系统的性能基石。

至于那六便士老板到底有没有给，霍尔后来回忆说他自己也记不太清了。

1961 年春天，霍尔参加了一个为期一周的 Algol 60 编程语言培训班，下午的练习时间，别人都在做老师布置的作业，霍尔却想试试能不能用 Algol 60 的递归特性来实现快速排序。

这份代码后来在 1962 年发表在《计算机杂志》（Computer Journal）上，成了霍尔的第三篇学术论文，也为他此后的学术生涯奠定了基础。

十亿美元的错误

快排算法让霍尔一举成名，但他对计算机科学的影响远不止于此。

1969 年，他提出了霍尔逻辑（Hoare Logic），这是一套用于验证程序正确性的形式化系统。

它提供了一组严谨的公理和推理规则，让开发者能用数学的方式证明一段代码确实在做它该做的事。这为后来整个软件可靠性和安全性研究打下了理论基础。

1978 年，他又提出了通信顺序进程（CSP）模型，专门用于描述并发系统中多个进程之间的交互行为。

这个模型后来直接影响了 Go 语言的并发设计，Go 语言中 goroutine 之间通过 channel 通信的核心思想，正是源自 CSP 模型。

1980 年，霍尔因 " 对程序设计语言的定义和设计的根本性贡献获得图灵奖。

图灵奖的颁奖词特别强调了编程语言设计的重要性：

构建软件的成本对社会而言极其高昂，而软件质量往往不尽如人意，相当一部分责任要归咎于编写软件所用的语言本身。许多让病毒等恶意软件趁虚而入的安全漏洞，原本可以通过使用更好的语言来避免。

霍尔在图灵奖演讲中反复传达了一个核心信息：简洁和优雅是软件保持在人类智力可控范围内的必要条件。

事实上，早在 1973 年，他就发表过一篇题为《程序设计语言设计的提示》（Hints on Programming Language Design）的论文，里面的建议至今仍被认为极具价值。

不过，霍尔留给世界的不只有正面遗产。

1965 年，他在设计 ALGOL W 语言时，引入了一个看似无害的概念：空引用（Null Reference）。

霍尔后来描述这个设计的初衷很简单，就是为了方便表示一个变量 " 没有值 "，而且它实现起来太容易了，几乎没有任何额外成本。

正因如此，空引用被后来的编程语言大量采纳，Java、C#、C++，几乎无一幸免。

但代价也随之而来：无数的 NullPointerException、系统崩溃、安全漏洞，几十年来在全世界的软件系统中反复上演。

2009 年，75 岁的霍尔在一次公开演讲中对此做出了坦诚的反思：

我称之为我十亿美元的错误。我无法抗拒引入空引用的诱惑，仅仅因为它太容易实现了。这导致了无数的错误、漏洞和系统崩溃，在过去的四十年里，可能造成了十亿美元的痛苦和损失。

一位图灵奖得主，公开承认自己犯了一个波及全行业数十年的设计错误，这在计算机科学界并不多见。

从古典学到计算机科学

霍尔的人生轨迹本身，也足够让人意外。

1934 年他出生于英属锡兰，也就是今天的斯里兰卡。进入牛津大学后，他最初学的是古典学和哲学。

毕业后服役期间，他在军队中学习了俄语，再加上一系列机缘巧合，才让他有去莫斯科学习的机会，才有了发明快速排序算法的故事。

服役归来，霍尔打算深入研究古典学中的数理逻辑和形式化，回到牛津读统计学硕士，第一次接触 Mercury Autocode 语言，正式入门编程。

霍尔的叔叔是英国皇家海军上校，退役后在英国科学仪器制造商协会担任秘书长。1960 年，协会在莫斯科办了一场科学仪器展览，叔叔知道侄子会说俄语、人又在莫斯科，就花 40 英镑请他去当翻译。

展览上，英国 Elliott Brothers 公司正在展出一台 803 型计算机。霍尔一有空就泡在那个展台上，结识了 Elliott 计算部门的总经理埃迪 · 纳什（Eddie Nash）。

纳什当场邀请他回英国后来公司上班，尽管霍尔当时的全部资历就是 " 会俄语、会拉丁语和希腊语 "

霍尔的第一篇科学论文是在莫斯科期间用俄语写的，发表在苏联的《机器翻译》杂志上。

论文署名时，他的姓氏 Hoare 被音译成了俄文 "XOAP"，因为俄语里根本没有 H 这个音。回译成英文后变成了 "Choar" 或者 "Khoar"。所以如果你想在文献索引里找到这篇论文，得去 C 或者 K 开头的条目下面翻。

从莫斯科回国前，英国国家物理实验室（NPL）曾给他发来一封信，邀请他担任高级科学官员，从事俄英自动翻译项目。霍尔的英国同学告诉他，这是一个非常体面的职位，能拿到这个 Offer 很幸运。

但当他真正回到英国去面试时，人事部门告诉他：因为你没有理科学位，所以永远不可能成为正式的科学类公务员。

他们只愿意以 " 临时技术官员 " 的身份雇用他——比当初承诺的职级低了两三档，而且永远没有晋升机会。

霍尔当即拒绝了。五年后，那个机器翻译项目以失败告终。

离开莫斯科时，纳什建议霍尔搭运电脑的空货车回英国，顺便沿途帮忙用俄语跟旅馆和边境打交道，霍尔欣然同意。

结果货车开出莫斯科才 30 英里，油门就坏了。检查发现连杆的一部分掉了，他们不得不用车身上拆下来的零件临时拼了一个替代品。但这个临时方案有个致命问题：油门的逻辑反了——想加速得松开踏板，想刹车得踩下去。

开了一个小时脚踝就受不了了，只能频繁换人驾驶。最惨的是路上的行人：每当有人试图横穿马路，司机的脚本能地移向刹车踏板，发动机却发出一声怒吼猛然加速，把行人吓得惊慌失措。

从莫斯科回来后，霍尔的职业生涯在工业界和学术界之间来回切换。

1960 年，他加入了 Elliott Brothers 公司，在那里领导团队完成了 ALGOL 60 编程语言的首个商用编译器开发，随后成为公司的首席科学家。

相比之下，Elliott 的纳什给了他标准的毕业生程序员年薪，800 英镑，外加 100 英镑的俄语津贴。纳什后来跟霍尔说过一句话：" 我觉得我为 Elliott 做过的最好的事情，就是把你招了进来。

1968 年，他转入学术界，先后在贝尔法斯特女王大学和牛津大学担任计算机科学教授。在牛津期间，他领导了著名的编程研究小组（Programming Research Group）长达 22 年。

在整理搬家的文件时，他翻到了鲍勃 · 弗洛伊德（Bob Floyd）1967 年发表的一篇论文《为程序赋予意义》（Assigning Meaning to Programs）。弗洛伊德提出了一种在程序流程图上添加断言的方法，使得证明程序符合规格成为可能。

霍尔在此基础上迈出了两步：

第一，他抛弃了流程图，发展出一套直接针对程序语句进行推理的逻辑系统，核心概念就是后来以他名字命名的 " 霍尔三元组 "（Hoare Triple）；

第二，他提出这套公理系统本身就可以作为记录编程语言语义的一种抽象方式。

这篇 1969 年发表的论文《计算机编程的公理基础》（An Axiomatic Basis for Computer Programming），成为编程理论领域最具影响力的论文之一。

它最深刻的意义在于：程序的正确性不再是写完之后再去 " 验证 " 的事后工作，而是可以在开发过程中同步 " 构造 " 出来。

霍尔最重要的理论贡献之一—— CSP 并发模型，源于一次失败。

在 Elliott Brothers 工作期间，他负责设计 Elliott 503 Mark II 的操作系统，但项目最终没能交付，直接导致了 503 计算机商业生命的终结。

霍尔后来坦率地承认，正是这次失败让他意识到并发程序有多难驾驭，从而促使他在此后的学术生涯中投入大量精力去理解和驯服并发问题。

当时程序之间的同步方式主要依赖共享变量，但霍尔发现，除非对共享施加严格的限制，否则几乎不可能穷尽所有可能出现的情况。

这类程序中的 bug 既难以捕捉又破坏力巨大。他曾尝试提出约束共享变量干扰的方案，但最终认定这条路根本走不通。

于是在 1978 年，他做出了一个大胆的转向：提出 CSP 模型，将程序之间的交互限制为预先规划好的通信，彻底抛弃了共享变量的思路。

1999 年从牛津退休后，他没有停下来，而是加入了微软剑桥研究院，担任高级研究员，一直活跃在研究一线。

他一生荣誉等身：

1980 年因 " 对程序设计语言的定义和设计的根本性贡献 " 获得图灵奖；

2000 年被英国女王伊丽莎白二世册封为爵士；

同年获得信息科学领域的京都奖；

2011 年又获颁 IEEE 约翰 · 冯 · 诺依曼奖章。

他还是英国皇家学会院士、英国皇家工程院院士以及美国国家工程院外籍院士。

霍尔去世的消息传出后，有曾在 1980 年代参加过他开设的算法分析暑期课程的网友留言：

我至今仍愉快地记得那门课，那是为期一周的高强度算法分析。安息吧，我们这个行业真正的巨人之一。

参考链接：

[ 1 ] https://blog.computationalcomplexity.org/2026/03/tony-hoare-1934-2026.html?m=1

[ 2 ] https://plus.maths.org/happy-birthday-quicksort-0

[ 3 ] http://codelabs.ru/boo/hoare.early-days-at-elliot.html

[ 4 ] https://amturing.acm.org/award_winners/hoare_4622167.cfm

—  欢迎 AI 产品从业者共建  —

「AI 产品知识库」是量子位智库基于长期产品库追踪和用户行为数据推出的飞书知识库，旨在成为 AI 行业从业者、投资者、研究者的核心信息枢纽与决策支持平台。

一键关注 点亮星标

科技前沿进展每日见