快排算法之父Tony Hoare去世，從古典學文科生出身到圖靈獎得主，他的人生比算法更傳奇

快排算法之父、圖靈獎得主托尼·霍爾（Tony Hoare）去世了，享年92歲。

凡是學過計算機的人，幾乎沒有誰能繞開快速排序（Quicksort）。

它是世界上使用最廣泛的排序算法之一，被寫進了幾乎所有主流編程語言的標準庫，從C到Java到Python，隨處可見它的身影。

快速排序只是他漫長學術生涯的起點。

他是1980年圖靈獎得主，提出了用數學方式證明程序正確性的霍爾邏輯，還創造了直接影響Go語言設計的CSP并發模型。

他還親手制造了后來被他自己稱為“十億美元的錯誤”的空引用（Null Reference），深刻影響了后世的Java、C++等語言。

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

快速排序的故事要從1959年說起。

那一年，25歲的霍爾還是個訪問學生，在莫斯科國立大學學習機器翻譯。

他參與的項目需要把俄語句子中的單詞排好序，然后去一卷磁帶上存儲的俄英詞典里查找對應的英文。

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

冒泡排序的原理很簡單：

給定一個需要排序的元素列表，首先比較前兩個元素，如果順序錯誤則交換它們。然后比較列表中的第2個和第3個元素，如果順序錯誤則交換它們。

以此類推，直到遍歷完整個列表，如果在此過程中無需交換任何元素，則說明列表已經排序正確，此時停止。

但很快，他就發現這個方法太慢了，時間復雜度是O(n2)，處理上規模的數據根本不夠用。

于是他開始琢磨一種全新的思路：

先從數組里選一個元素當“基準”，然后把比它小的全部挪到左邊，比它大的全部挪到右邊，接著對左右兩部分各自重復這個過程。

也就是“分而治之”，把一個大問題拆成小問題，遞歸解決。

回到英國后，他的同事對此表示懷疑，掏出六便士跟他打賭，不信他能找到比當時流行的希爾排序（Shellsort）更快的算法。

希爾排序是插入排序的升級版。最簡單的插入排序就像整理撲克牌一樣，逐個把牌插入到前面已經排好序的對應位置。

但在計算機算法中，如果數組里的元素“離自己該在的位置很遠”，每個元素都要一步一步往前挪，效率極低。

希爾排序的做法是先粗略分組整理，再精細微調。設置一個步長把數組分成多個子數組，對每個子數組做插入排序；然后逐步縮小步長，直到步長為1。

希爾排序的時間復雜度最壞情況為O(n2)，最好情況為O(n log n)，平均情況在O(n log n)到O(n2)之間。

霍爾用了一個下午的時間完善了快速排序的細節，贏下了這場賭局。

事實證明，快速排序的平均時間復雜度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

文章來源：量子位。