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

凡是學(xué)過(guò)計(jì)算機(jī)的人，幾乎沒(méi)有誰(shuí)能繞開(kāi)快速排序（Quicksort）。

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

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

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

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

在莫斯科“排”出來(lái)的算法

快速排序的故事要從1959年說(shuō)起。

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

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

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

冒泡排序的原理很簡(jiǎn)單：

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

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

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

于是他開(kāi)始琢磨一種全新的思路：

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

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

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

希爾排序是插入排序的升級(jí)版。最簡(jiǎn)單的插入排序就像整理?yè)淇伺埔粯?，逐個(gè)把牌插入到前面已經(jīng)排好序的對(duì)應(yīng)位置。

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

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

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

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

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

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

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

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

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

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

至于那六便士老板到底有沒(méi)有給，霍爾后來(lái)回憶說(shuō)他自己也記不太清了。

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

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

十億美元的錯(cuò)誤

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

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

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

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

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

1980年，霍爾因“對(duì)程序設(shè)計(jì)語(yǔ)言的定義和設(shè)計(jì)的根本性貢獻(xiàn)獲得圖靈獎(jiǎng)。

圖靈獎(jiǎng)的頒獎(jiǎng)詞特別強(qiáng)調(diào)了編程語(yǔ)言設(shè)計(jì)的重要性：

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

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

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

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

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

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

正因如此，空引用被后來(lái)的編程語(yǔ)言大量采納，Java、C#、C++，幾乎無(wú)一幸免。

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

2009年，75歲的霍爾在一次公開(kāi)演講中對(duì)此做出了坦誠(chéng)的反思：

我稱之為我十億美元的錯(cuò)誤。我無(wú)法抗拒引入空引用的誘惑，僅僅因?yàn)樗菀讓?shí)現(xiàn)了。這導(dǎo)致了無(wú)數(shù)的錯(cuò)誤、漏洞和系統(tǒng)崩潰，在過(guò)去的四十年里，可能造成了十億美元的痛苦和損失。

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

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

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

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

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

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

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

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

納什當(dāng)場(chǎng)邀請(qǐng)他回英國(guó)后來(lái)公司上班，盡管霍爾當(dāng)時(shí)的全部資歷就是”會(huì)俄語(yǔ)、會(huì)拉丁語(yǔ)和希臘語(yǔ)”

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

論文署名時(shí)，他的姓氏Hoare被音譯成了俄文”XOAP”，因?yàn)槎碚Z(yǔ)里根本沒(méi)有H這個(gè)音?；刈g成英文后變成了”Choar”或者”Khoar”。所以如果你想在文獻(xiàn)索引里找到這篇論文，得去C或者K開(kāi)頭的條目下面翻。

從莫斯科回國(guó)前，英國(guó)國(guó)家物理實(shí)驗(yàn)室（NPL）曾給他發(fā)來(lái)一封信，邀請(qǐng)他擔(dān)任高級(jí)科學(xué)官員，從事俄英自動(dòng)翻譯項(xiàng)目?；魻柕挠?guó)同學(xué)告訴他，這是一個(gè)非常體面的職位，能拿到這個(gè)Offer很幸運(yùn)。

但當(dāng)他真正回到英國(guó)去面試時(shí)，人事部門告訴他：因?yàn)槟銢](méi)有理科學(xué)位，所以永遠(yuǎn)不可能成為正式的科學(xué)類公務(wù)員。

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

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

離開(kāi)莫斯科時(shí)，納什建議霍爾搭運(yùn)電腦的空貨車回英國(guó)，順便沿途幫忙用俄語(yǔ)跟旅館和邊境打交道，霍爾欣然同意。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

他一生榮譽(yù)等身：

• 1980年因“對(duì)程序設(shè)計(jì)語(yǔ)言的定義和設(shè)計(jì)的根本性貢獻(xiàn)”獲得圖靈獎(jiǎng)；

• 2000年被英國(guó)女王伊麗莎白二世冊(cè)封為爵士；

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

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

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

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

我至今仍愉快地記得那門課，那是為期一周的高強(qiáng)度算法分析。安息吧，我們這個(gè)行業(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

文章來(lái)源：量子位。