快排算法之父托尼·霍尔逝世，他创造的“十亿美元错误”如何影响编程世界？

快排算法之父、图灵奖得主托尼·霍尔逝世，享年92岁

在计算机科学领域，几乎无人能绕开快速排序算法。作为全球使用最广泛的排序算法之一，它已被集成进从C、Java到Python等几乎所有主流编程语言的标准库中。

然而，快速排序仅仅是托尼·霍尔漫长而卓越学术生涯的起点。作为1980年图灵奖得主，他提出了用于形式化验证程序正确性的霍尔逻辑，创造了深刻影响Go语言设计的通信顺序进程（CSP）并发模型。同时，他也因引入了被自己称为“十亿美元错误”的空引用概念，而对Java、C++等后世编程语言产生了深远影响。

诞生于莫斯科的算法

快速排序的故事始于1959年。当时，25岁的霍尔作为访问学生，在莫斯科国立大学学习机器翻译。

他参与的项目需要将俄语句子中的单词排序，以便在一卷存储俄英词典的磁带上进行查找。排序是第一步，霍尔最初想到的是冒泡排序法。

冒泡排序的原理简单直接：遍历元素列表，比较相邻元素并交换顺序错误的项，直至整个列表有序。若某次遍历未发生交换，则排序完成。但霍尔很快意识到，其O(n²)的时间复杂度在处理大规模数据时效率过低。

于是，他构思了一种全新的思路：从数组中选取一个“基准”元素，将小于基准的元素移至其左侧，大于基准的移至右侧，然后对左右两个子数组递归地重复此过程。这种“分而治之”的策略，将大问题分解为小问题逐一解决。

返回英国后，同事对他的新方法表示怀疑，并以六便士打赌，认为其不可能快于当时流行的希尔排序。希尔排序是插入排序的改进版，通过设定步长分组排序再逐步缩小步长来提升效率，其时间复杂度介于O(n log n)到O(n²)之间。

霍尔用一个下午完善了快速排序的细节，并赢得了赌注。事实证明，快速排序的平均时间复杂度为O(n log n)，仅在极少数情况下慢于希尔排序。此外，作为原地排序算法，它仅需O(log n)的辅助空间，且其对现代计算机缓存机制（时间局部性与空间局部性）的良好适应性，使其在实际运行中往往更快。

自1960年代起，快速排序便成为计算机科学教育的核心内容，也是无数软件与数据库系统的性能基石。至于那六便士赌注是否兑现，霍尔晚年回忆称已记不清了。

1961年，霍尔在一次Algol 60编程语言培训中，利用该语言的递归特性实现了快速排序。相关代码于1962年发表在《计算机杂志》上，成为他的第三篇学术论文，为其学术生涯奠定了重要基础。

“十亿美元的错误”

快速排序让霍尔声名鹊起，但其贡献远不止于此。

1969年，他提出霍尔逻辑，为一套用于严格证明程序正确性的形式化系统奠定了基础，极大地推动了软件可靠性与安全性研究。

1978年，他提出通信顺序进程模型，为描述并发系统进程交互提供了框架。此模型直接启发了Go语言以channel为核心的并发设计。

1980年，霍尔因“对程序设计语言的定义和设计的基础性贡献”荣获图灵奖。颁奖词指出，编程语言本身的缺陷是导致软件成本高昂、质量不佳及安全漏洞的重要原因。

在图灵奖演讲及1973年的论文《程序设计语言设计的提示》中，霍尔始终强调简洁与优雅是保持软件可控于人类智力范围内的关键。

然而，霍尔也留下了一项影响深远的争议设计。1965年，他在设计ALGOL W语言时，为方便表示“无值”状态，引入了空引用。因其实现简单，该概念后被Java、C#、C++等众多语言广泛采纳，但也随之引发了无数的空指针异常、系统崩溃与安全漏洞。

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

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

一位图灵奖得主如此公开承认一个波及全行业数十年的设计错误，在计算机科学界实属罕见。

从古典学者到计算机先驱

霍尔的人生轨迹同样非凡。1934年他出生于英属锡兰（今斯里兰卡），在牛津大学最初攻读古典学与哲学。毕业后服役期间学习了俄语，这为他后来前往莫斯科学习并发明快速排序算法创造了契机。

退役后，霍尔为深入研究古典学中的形式逻辑，返回牛津攻读统计学硕士，并首次接触Mercury Autocode语言，正式步入编程世界。

1960年，因其俄语能力，霍尔受雇在莫斯科的一场英国科学仪器展览上担任翻译。期间，他结识了Elliott Brothers公司计算部门的总经理，并获得了回国后加入该公司的邀请——尽管他当时的资历仅是“会俄语、拉丁语和希腊语”。

霍尔的第一篇科学论文在莫斯科期间以俄语写成，发表于苏联《机器翻译》杂志。由于俄语音译，其姓氏“Hoare”在论文索引中需在“C”或“K”条目下查找。

在从莫斯科回国前，英国国家物理实验室曾向他发出担任高级科学官员的邀请，从事俄英自动翻译项目。这份工作在当时被视作一份非常体面的职位。

但当他回到英国面试时，人事部门却告知：由于没有理科学位，他永远无法成为正式的科学类公务员。

对方只愿以“临时技术官员”的身份雇用他——职级比最初承诺的低了两三档，且没有晋升机会。霍尔当即拒绝。五年后，那个机器翻译项目以失败告终。

离开莫斯科时，纳什建议霍尔搭乘运送电脑的空货车返回英国，途中可帮忙用俄语与旅馆和边境沟通，霍尔欣然同意。

然而货车驶离莫斯科仅30英里，油门便发生故障。检查发现连杆部分脱落，他们不得不从车身上拆下零件拼凑出一个临时替代品。但这方案存在一个致命问题：油门逻辑反了——想加速需松开踏板，想刹车却要踩下去。

驾驶一小时后脚踝已难以承受，只得频繁更换司机。最遭殃的是路上行人：每当有人试图横穿马路，司机本能移向刹车踏板，发动机却发出怒吼猛然加速，吓得行人惊慌失措。

自莫斯科归来，霍尔的职业生涯在工业界与学术界之间辗转。

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

相比之下，Elliott的纳什为他提供了标准的毕业生程序员年薪——800英镑，外加100英镑俄语津贴。纳什后来对霍尔说：“我认为我为Elliott做过最好的事，就是招你进来。”

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

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

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

第一，他抛弃流程图，发展出一套直接针对程序语句进行推理的逻辑系统，核心即后来以他命名的“霍尔三元组”；

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

1969年发表的论文《计算机编程的公理基础》，成为编程理论领域最具影响力的论文之一。

其最深刻的意义在于：程序的正确性不再是编写完成后才去“验证”的事后工作，而是能在开发过程中同步“构造”出来。

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

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

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

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

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

于是在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资讯