快速排序算法 - 快速排序是世界上使用最广泛的排序算法之一，被写进了几乎所有主流编程语言的标准库，如C、Java、Python [2][3] - 该算法由托尼·霍尔于1959年在莫斯科学习期间构思，旨在解决机器翻译项目中俄语单词排序的效率问题 [5][6][8] - 算法核心思路是“分而治之”，选择一个基准元素，将小于它的元素移到左边，大于它的移到右边，然后递归处理左右两部分 [13] - 其平均时间复杂度为O(n log n)，是原地排序算法，仅需O(log n)的辅助空间，且对现代计算机缓存机制友好，实际运行速度快 [19][20][21] - 霍尔用一下午时间完善算法细节，并在一场与同事关于希尔排序速度的赌局中获胜，赢下六便士 [14][18] 霍尔的其他学术贡献 - 于1969年提出霍尔逻辑，这是一套用于验证程序正确性的形式化系统，为软件可靠性和安全性研究奠定了理论基础 [28] - 于1978年提出通信顺序进程模型，该模型专门用于描述并发系统中多个进程间的交互行为，并直接影响了Go语言中goroutine与channel的并发设计 [30][31] - 于1969年发表论文《计算机编程的公理基础》，提出了“霍尔三元组”概念，使程序的正确性可在开发过程中同步构造，成为编程理论领域最具影响力的论文之一 [61][62] - 其1961年用Algol 60语言实现的快速排序代码于1962年发表在《计算机杂志》上，成为其第三篇学术论文 [25] 空引用及其影响 - 霍尔于1965年在设计ALGOL W语言时引入了空引用概念，初衷是为了方便表示变量“没有值”，且实现成本极低 [41][42] - 此设计被后来的Java、C、C++等主流编程语言大量采纳 [43] - 霍尔在2009年的一次公开演讲中反思，称其为“十亿美元的错误”，指出它导致了无数的错误、漏洞、系统崩溃，在过去四十年可能造成了十亿美元的损失 [45] 霍尔的职业生涯与荣誉 - 霍尔最初在牛津大学学习古典学和哲学，后因在军队学习俄语，得以在莫斯科国立大学学习机器翻译 [50][51] - 1960年，他加入英国Elliott Brothers公司，领导团队完成了ALGOL 60编程语言的首个商用编译器开发，并成为公司首席科学家 [60] - 1968年转入学术界，先后在贝尔法斯特女王大学和牛津大学担任计算机科学教授，并在牛津领导编程研究小组长达22年 [60] - 1999年从牛津退休后，加入微软剑桥研究院担任高级研究员 [68] - 他于1980年因“对程序设计语言的定义和设计的根本性贡献”获得图灵奖 [35] - 他还曾获得京都奖、IEEE约翰·冯·诺依曼奖章，并被英国女王伊丽莎白二世册封为爵士 [74]