从古典学到图灵奖——快排算法之父Tony Hoare量子位

快排算法之父、1980 年图灵奖得主托尼・霍尔（Tony Hoare）与世长辞，享年 92 岁。

凡是学过计算机的人，几乎没有谁能绕开他发明的快速排序（Quicksort）—— 这是世界上使用最广泛的排序算法之一，被写进了 C、Java、Python 等几乎所有主流编程语言的标准库，成为软件和数据库系统的性能基石。

快速排序只是他漫长学术生涯的起点。作为计算机科学领域的巨擘，他提出了用数学方式证明程序正确性的霍尔逻辑，创造了直接影响 Go 语言设计的 CSP 并发模型；同时，他也坦诚自己发明的 “空引用（Null Reference）” 是 “十亿美元的错误”，深刻影响了后世众多编程语言。

在莫斯科 “排” 出来的算法

快速排序的诞生颇具传奇色彩，故事要从 1959 年说起。那一年，25 岁的霍尔以访问学生身份在莫斯科国立大学学习机器翻译，他参与的项目需要先对俄语句子中的单词排序，再去磁带上的俄英词典中查找对应英文。

排序是项目的第一步，霍尔最初想到的是冒泡排序。这种算法的原理很简单：给定元素列表，依次比较相邻元素，顺序错误则交换，重复遍历直到无需交换。但冒泡排序的时间复杂度为 O (n²)，处理大规模数据时效率极低，根本无法满足项目需求。

于是他开始琢磨全新思路：先从数组中选一个元素作为 “基准”，将比基准小的元素挪到左边，比基准大的挪到右边，再对左右两部分递归重复这一过程 —— 这就是 “分而治之” 思想的经典应用。

回到英国后，同事对这套算法表示怀疑，甚至掏出六便士打赌，不信他能找到比当时流行的希尔排序更快的方案。希尔排序作为插入排序的升级版，通过设置步长分组排序再逐步微调，最坏时间复杂度为 O (n²)，最好情况为 O (n log n)，平均情况介于两者之间。

霍尔仅用一个下午完善细节，便赢下了赌局。事实证明，快速排序的平均时间复杂度为 O (n log n)，仅在极少数情况下比希尔排序慢；且它是原地排序，仅需 O (log n) 的辅助空间，无需像归并排序那样额外开辟 O (n) 内存；更重要的是，它完美契合现代计算机的缓存机制（遵循时间局部性和空间局部性），实际运行速度往往优于同等复杂度的其他算法。

1961 年春天，霍尔在 Algol 60 编程语言培训班上，利用练习时间用该语言的递归特性实现了快速排序。这份代码于 1962 年发表在《计算机杂志》（Computer Journal）上，成为他的第三篇学术论文，也为其学术生涯奠定了坚实基础。

不止快排：影响深远的学术贡献

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

1969 年，他提出了霍尔逻辑（Hoare Logic），这是一套用于验证程序正确性的形式化系统。它提供了严谨的公理和推理规则，让开发者能用数学方式证明代码是否符合预期功能，为软件可靠性和安全性研究打下了理论基础。