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

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

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

快速排序只是他漫長學(xué)術(shù)生涯的起點。

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

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

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

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

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

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

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

冒泡排序的原理很簡單：

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

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

但很快，他就發(fā)現(xiàn)這個方法太慢了，時間復(fù)雜度是O(n2)，處理上規(guī)模的數(shù)據(jù)根本不夠用。

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

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

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

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

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

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

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

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

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

事實證明，快速排序的平均時間復(fù)雜度O(n log n)，只在極少情況下比希爾排序慢。

并且由于快速排序是原地排序，只需要O(log n)的輔助空間，不像歸并排序那樣需要額外開辟一整塊O(n)的內(nèi)存。

再加上它對現(xiàn)代計算機緩存機制格外友好，實際運行速度往往比同等復(fù)雜度的其他算法更快。

緩存的設(shè)計遵循時間局部性和空間局部性。訪問一個數(shù)據(jù)時，它附近的連續(xù)數(shù)據(jù)大概率也會被訪問。近期訪問過的數(shù)據(jù)，大概率會被再次訪問。

快速排序完美契合這兩個特性，就像整理一摞連續(xù)擺放的文件，手邊（緩存）一次放10份，不用來回跑。

從1960年代至今，快速排序已經(jīng)成為計算機科學(xué)教育中繞不開的內(nèi)容，也是無數(shù)軟件和數(shù)據(jù)庫系統(tǒng)的性能基石。

至于那六便士老板到底有沒有給，霍爾后來回憶說他自己也記不太清了。

1961年春天，霍爾參加了一個為期一周的Algol 60編程語言培訓(xùn)班，下午的練習(xí)時間，別人都在做老師布置的作業(yè)，霍爾卻想試試能不能用Algol 60的遞歸特性來實現(xiàn)快速排序。

這份代碼后來在1962年發(fā)表在《計算機雜志》（Computer Journal）上，成了霍爾的第三篇學(xué)術(shù)論文，也為他此后的學(xué)術(shù)生涯奠定了基礎(chǔ)。

十億美元的錯誤

快排算法讓霍爾一舉成名，但他對計算機科學(xué)的影響遠(yuǎn)不止于此。

1969年，他提出了霍爾邏輯（Hoare Logic），這是一套用于驗證程序正確性的形式化系統(tǒng)。

它提供了一組嚴(yán)謹(jǐn)?shù)墓砗屯评硪?guī)則，讓開發(fā)者能用數(shù)學(xué)的方式證明一段代碼確實在做它該做的事。這為后來整個軟件可靠性和安全性研究打下了理論基礎(chǔ)。

1978年，他又提出了通信順序進程（CSP）模型，專門用于描述并發(fā)系統(tǒng)中多個進程之間的交互行為。

這個模型后來直接影響了Go語言的并發(fā)設(shè)計，Go語言中g(shù)oroutine之間通過channel通信的核心思想，正是源自CSP模型。

1980年，霍爾因“對程序設(shè)計語言的定義和設(shè)計的根本性貢獻獲得圖靈獎。

圖靈獎的頒獎詞特別強調(diào)了編程語言設(shè)計的重要性：

構(gòu)建軟件的成本對社會而言極其高昂，而軟件質(zhì)量往往不盡如人意，相當(dāng)一部分責(zé)任要歸咎于編寫軟件所用的語言本身。許多讓病毒等惡意軟件趁虛而入的安全漏洞，原本可以通過使用更好的語言來避免。

霍爾在圖靈獎演講中反復(fù)傳達了一個核心信息：簡潔和優(yōu)雅是軟件保持在人類智力可控范圍內(nèi)的必要條件。

事實上，早在1973年，他就發(fā)表過一篇題為《程序設(shè)計語言設(shè)計的提示》（Hints on Programming Language Design）的論文，里面的建議至今仍被認(rèn)為極具價值。

不過，霍爾留給世界的不只有正面遺產(chǎn)。

1965年，他在設(shè)計ALGOL W語言時，引入了一個看似無害的概念：空引用（Null Reference）。

霍爾后來描述這個設(shè)計的初衷很簡單，就是為了方便表示一個變量“沒有值”，而且它實現(xiàn)起來太容易了，幾乎沒有任何額外成本。

正因如此，空引用被后來的編程語言大量采納，Java、C#、C++，幾乎無一幸免。

但代價也隨之而來：無數(shù)的NullPointerException、系統(tǒng)崩潰、安全漏洞，幾十年來在全世界的軟件系統(tǒng)中反復(fù)上演。

2009年，75歲的霍爾在一次公開演講中對此做出了坦誠的反思：

我稱之為我十億美元的錯誤。我無法抗拒引入空引用的誘惑，僅僅因為它太容易實現(xiàn)了。這導(dǎo)致了無數(shù)的錯誤、漏洞和系統(tǒng)崩潰，在過去的四十年里，可能造成了十億美元的痛苦和損失。

一位圖靈獎得主，公開承認(rèn)自己犯了一個波及全行業(yè)數(shù)十年的設(shè)計錯誤，這在計算機科學(xué)界并不多見。

從古典學(xué)到計算機科學(xué)

霍爾的人生軌跡本身，也足夠讓人意外。

1934年他出生于英屬錫蘭，也就是今天的斯里蘭卡。進入牛津大學(xué)后，他最初學(xué)的是古典學(xué)和哲學(xué)。

畢業(yè)后服役期間，他在軍隊中學(xué)習(xí)了俄語，再加上一系列機緣巧合，才讓他有去莫斯科學(xué)習(xí)的機會，才有了發(fā)明快速排序算法的故事。

服役歸來，霍爾打算深入研究古典學(xué)中的數(shù)理邏輯和形式化，回到牛津讀統(tǒng)計學(xué)碩士，第一次接觸Mercury Autocode語言，正式入門編程。

霍爾的叔叔是英國皇家海軍上校，退役后在英國科學(xué)儀器制造商協(xié)會擔(dān)任秘書長。1960年，協(xié)會在莫斯科辦了一場科學(xué)儀器展覽，叔叔知道侄子會說俄語、人又在莫斯科，就花40英鎊請他去當(dāng)翻譯。

展覽上，英國Elliott Brothers公司正在展出一臺803型計算機?；魻栆挥锌站团菰谀莻€展臺上，結(jié)識了Elliott計算部門的總經(jīng)理埃迪·納什（Eddie Nash）。

納什當(dāng)場邀請他回英國后來公司上班，盡管霍爾當(dāng)時的全部資歷就是”會俄語、會拉丁語和希臘語”

霍爾的第一篇科學(xué)論文是在莫斯科期間用俄語寫的，發(fā)表在蘇聯(lián)的《機器翻譯》雜志上。

論文署名時，他的姓氏Hoare被音譯成了俄文”XOAP”，因為俄語里根本沒有H這個音?；刈g成英文后變成了”Choar”或者”Khoar”。所以如果你想在文獻索引里找到這篇論文，得去C或者K開頭的條目下面翻。

從莫斯科回國前，英國國家物理實驗室（NPL）曾給他發(fā)來一封信，邀請他擔(dān)任高級科學(xué)官員，從事俄英自動翻譯項目?；魻柕挠瑢W(xué)告訴他，這是一個非常體面的職位，能拿到這個Offer很幸運。

但當(dāng)他真正回到英國去面試時，人事部門告訴他：因為你沒有理科學(xué)位，所以永遠(yuǎn)不可能成為正式的科學(xué)類公務(wù)員。

他們只愿意以”臨時技術(shù)官員”的身份雇用他——比當(dāng)初承諾的職級低了兩三檔，而且永遠(yuǎn)沒有晉升機會。

霍爾當(dāng)即拒絕了。五年后，那個機器翻譯項目以失敗告終。

離開莫斯科時，納什建議霍爾搭運電腦的空貨車回英國，順便沿途幫忙用俄語跟旅館和邊境打交道，霍爾欣然同意。

結(jié)果貨車開出莫斯科才30英里，油門就壞了。檢查發(fā)現(xiàn)連桿的一部分掉了，他們不得不用車身上拆下來的零件臨時拼了一個替代品。但這個臨時方案有個致命問題：油門的邏輯反了——想加速得松開踏板，想剎車得踩下去。

開了一個小時腳踝就受不了了，只能頻繁換人駕駛。最慘的是路上的行人：每當(dāng)有人試圖橫穿馬路，司機的腳本能地移向剎車踏板，發(fā)動機卻發(fā)出一聲怒吼猛然加速，把行人嚇得驚慌失措。

從莫斯科回來后，霍爾的職業(yè)生涯在工業(yè)界和學(xué)術(shù)界之間來回切換。

1960年，他加入了Elliott Brothers公司，在那里領(lǐng)導(dǎo)團隊完成了ALGOL 60編程語言的首個商用編譯器開發(fā)，隨后成為公司的首席科學(xué)家。

相比之下，Elliott的納什給了他標(biāo)準(zhǔn)的畢業(yè)生程序員年薪，800英鎊，外加100英鎊的俄語津貼。納什后來跟霍爾說過一句話：”我覺得我為Elliott做過的最好的事情，就是把你招了進來。

1968年，他轉(zhuǎn)入學(xué)術(shù)界，先后在貝爾法斯特女王大學(xué)和牛津大學(xué)擔(dān)任計算機科學(xué)教授。在牛津期間，他領(lǐng)導(dǎo)了著名的編程研究小組（Programming Research Group）長達22年。

在整理搬家的文件時，他翻到了鮑勃·弗洛伊德（Bob Floyd）1967年發(fā)表的一篇論文《為程序賦予意義》（Assigning Meaning to Programs）。弗洛伊德提出了一種在程序流程圖上添加斷言的方法，使得證明程序符合規(guī)格成為可能。

霍爾在此基礎(chǔ)上邁出了兩步：

第一，他拋棄了流程圖，發(fā)展出一套直接針對程序語句進行推理的邏輯系統(tǒng)，核心概念就是后來以他名字命名的“霍爾三元組”（Hoare Triple）；

第二，他提出這套公理系統(tǒng)本身就可以作為記錄編程語言語義的一種抽象方式。

這篇1969年發(fā)表的論文《計算機編程的公理基礎(chǔ)》（An Axiomatic Basis for Computer Programming），成為編程理論領(lǐng)域最具影響力的論文之一。

它最深刻的意義在于：程序的正確性不再是寫完之后再去“驗證”的事后工作，而是可以在開發(fā)過程中同步“構(gòu)造”出來。

霍爾最重要的理論貢獻之一——CSP并發(fā)模型，源于一次失敗。

在Elliott Brothers工作期間，他負(fù)責(zé)設(shè)計Elliott 503 Mark II的操作系統(tǒng)，但項目最終沒能交付，直接導(dǎo)致了503計算機商業(yè)生命的終結(jié)。

霍爾后來坦率地承認(rèn)，正是這次失敗讓他意識到并發(fā)程序有多難駕馭，從而促使他在此后的學(xué)術(shù)生涯中投入大量精力去理解和馴服并發(fā)問題。

當(dāng)時程序之間的同步方式主要依賴共享變量，但霍爾發(fā)現(xiàn)，除非對共享施加嚴(yán)格的限制，否則幾乎不可能窮盡所有可能出現(xiàn)的情況。

這類程序中的bug既難以捕捉又破壞力巨大。他曾嘗試提出約束共享變量干擾的方案，但最終認(rèn)定這條路根本走不通。

于是在1978年，他做出了一個大膽的轉(zhuǎn)向：提出CSP模型，將程序之間的交互限制為預(yù)先規(guī)劃好的通信，徹底拋棄了共享變量的思路。

1999年從牛津退休后，他沒有停下來，而是加入了微軟劍橋研究院，擔(dān)任高級研究員，一直活躍在研究一線。

他一生榮譽等身：

• 1980年因“對程序設(shè)計語言的定義和設(shè)計的根本性貢獻”獲得圖靈獎；

• 2000年被英國女王伊麗莎白二世冊封為爵士；

• 同年獲得信息科學(xué)領(lǐng)域的京都獎；

• 2011年又獲頒IEEE約翰·馮·諾依曼獎?wù)隆?/p>

他還是英國皇家學(xué)會院士、英國皇家工程院院士以及美國國家工程院外籍院士。

霍爾去世的消息傳出后，有曾在1980年代參加過他開設(shè)的算法分析暑期課程的網(wǎng)友留言：

我至今仍愉快地記得那門課，那是為期一周的高強度算法分析。安息吧，我們這個行業(yè)真正的巨人之一。

參考鏈接：
[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

文章來源：量子位。