快速排序里的學問:霍爾與快速排序

再次深入理解快速排序
服務器君一共花費了258.987 ms進行了7次數據庫查詢,努力地為您提供了這個頁面。
試試閱讀模式?希望聽取您的建議

上一篇介紹了排序的本質,還有實現了《算法導論》里的快速排序算法。但是快速排序的算法不是只有一個,我們要一次過把快速排序的好東西都挖掘出來。所以這篇文章,讓我們對快速排序溯源,去了解快速排序算法的發明者。

霍爾(Hoare)

霍爾 (Sir Charles Antony Richard Hoare) 是一位英國計算機科學家,他是著名的快速排序 (QuickSort) 的發明者。在平均狀況下,排序 n 個項目要Ο(n log n) 次比較,而且通常明顯比其他Ο(n log n) 演算法更快。所以它是一個被廣泛使用的算法。在一次采訪中,霍爾談到了發明這個算法的背景。

霍爾出生于斯里蘭卡。1956年畢業于牛津大學。然后的兩年里他在英國皇家海軍服役,他的任務是研究俄國的現代軍事,并因此開始學習了俄語。結束服役后, 他作為研究生進入莫斯科大學,主攻計算機翻譯。在莫斯科學習了一年。在這個時候正好有一家生產小型科學計算機的公司Elliott Brothers在那里舉辦展覽,霍爾為他們做翻譯。當他回國后,這家公司立即聘用了他,連面試都免了。他們還增加了他的工資,因為他會俄語。 Elliott Brothers讓霍爾設計一個新的計算機語言。但當他偶爾看到了一篇艾倫·佩利的“算法語言Algol 60報告”(Report on the Algorithmic Language Algol 60)后,他立即推薦公司放棄設計一個新的語言而轉為實施ALGOL。公司采納了他的建議。ALGOL是第一個清晰定義的語言,其語法是用嚴格公式化的方 法說明的。ALGOL語言并沒有被廣泛的使用,但它是許多現代程序語言的概念基礎。對他個人來說,這個項目不僅為他的事業奠定了基礎,還為他帶來了甜蜜的婚姻:他跟同組的同事Jill相識并結婚,成為一段美談。

言歸正傳。1960年代,英國國家物理實驗室 (National Physical Laboratory) 開始了一項新的計劃:將俄文自動翻譯成英文。正好霍爾有這個經歷,他與俄國的機器翻譯專家相識,還在“機器翻譯”(Machine Translation) 上發表過論文。于是他在那里得到了一份工作。

在那個年代,俄文到英文的詞匯列表是以字母順序存儲在一條長長的磁帶上的。因此,當有一段俄文句子需要翻譯時,第一步是把這個句子的詞按照同樣的順序排列。這樣機器就可以在磁帶上只走一遍就可以找到所有的翻譯。霍爾意識到,他必須找出一種能在計算機上實現的排序的算法來。他想到的第一個算法是后人稱作“冒泡排序?(bubble sort)”的算法。雖然他沒有聲明這個算法是他發明的,但他顯然是獨自得到這個算法的。他很快放棄了這個算法,因為它的速度比較慢。用計算復雜度理論(Computational complexity theory) 來說,它平均需要?O(n2)?次運算。快速排序?(Quicksort) 是霍爾想到的第二個算法。這個算法的計算復雜度是?O(nlogn)?次運算。當?n?特別大的時候,顯然步驟要少很多。這個算法是二十世紀七大算法之一,而他本人則被稱為影響算法世界的十位大師之一。霍爾自己則認為這個算法是他一生來得到的唯一一個有意義的算法。顯然他是謙虛了。太謙虛了!他在計算機語言和數理邏輯上建樹頗多。比如,黃富強老師介紹過霍爾邏輯?(Hoare logic)。當時就說我也要寫一篇介紹霍爾的文章,沒想到竟然拖到現在。

計算機歷史博物館真是一個好去處。還記得我以前寫的“建造一架150年前設計的差分機”嗎?也是在那里看到的。北京師范大學數學系的王世強教授和沈復興教授等對“計算復雜度”有一定的研究。我也是從他們那里第一次接觸到“計算復雜度”這個問題的。

回到“快速排序法”,其實“快速排序法”的基本思想是用遞歸 (Recursion),每進行一步都將一個大的集合劃分為兩個小的子集,然后對兩個子集實施相同的算法。當兩個子集都完成了排序之后再把它們重新粘合到一起。讓我們用下面的一個簡單例子簡單說明一下。

假定我們有一組10個數,我們希望將它們從小到大排列。
我們首先從數列中隨機挑出一個元素,稱為 "基準"(pivot)。
我們把比這個基準小的數放在左邊,把比這個基準大的數放在右邊。

上面是我們的第一步。在這一步之后,我們得到了兩個小的集合。現在我們重復上面的步驟對這兩個小的集合進行排序。這就是我前面說的遞歸的思想。讓我們忽略里面的具體細節。經過一些步驟之后,我們已經將這兩個小的集合排好序了。下面的兩步就容易理解了。

我把這段故事寫出來,希望軟件工程師們在學習計算方法時得到一些樂趣。也希望上面的故事和這個小例子能對大家有所幫助。

后注:1991年,楊正瓴老師發現了平均復雜性為 O(nloglogn)的自適應排序算法,以及對獨立同分布隨機數最壞時間幾乎處處為O(n)的排序算法。

延伸閱讀

此文章所在專題列表如下:

  1. 快速排序里的學問:從猜數字開始
  2. 快速排序里的學問:再看看稱球問題
  3. 快速排序里的學問:信息熵
  4. 快速排序里的學問:快速排序的過程
  5. 快速排序里的學問:霍爾與快速排序
  6. 快速排序里的學問:霍爾快排的實現
  7. 快速排序里的學問:樞紐元選擇與算法效率
  8. 快速排序里的學問:隨機化快排

本文地址:http://www.snpmgr.live/librarys/veda/detail/2391,歡迎訪問原出處。

不打個分嗎?

轉載隨意,但請帶上本文地址:

http://www.snpmgr.live/librarys/veda/detail/2391

如果你認為這篇文章值得更多人閱讀,歡迎使用下面的分享功能。
小提示:您可以按快捷鍵 Ctrl + D,或點此 加入收藏

大家都在看

閱讀一百本計算機著作吧,少年

很多人覺得自己技術進步很慢,學習效率低,我覺得一個重要原因是看的書少了。多少是多呢?起碼得看3、4、5、6米吧。給個具體的數量,那就100本書吧。很多人知識結構不好而且不系統,因為在特定領域有一個足夠量的知識量+足夠良好的知識結構,系統化以后就足以應對大量未曾遇到過的問題。

奉勸自學者:構建特定領域的知識結構體系的路徑中再也沒有比學習該專業的專業課程更好的了。如果我的知識結構體系足以囊括面試官的大部分甚至吞并他的知識結構體系的話,讀到他言語中的一個詞我們就已經知道他要表達什么,我們可以讓他坐“上位”畢竟他是面試官,但是在知識結構體系以及心理上我們就居高臨下。

所以,閱讀一百本計算機著作吧,少年!

《深入理解計算機系統(原書第2版)》 布萊恩特(Randal E.Bryant) (作者), 奧哈拉倫(David R.O'Hallaron) (作者), 龔奕利 (譯者), 雷迎春 (譯者)

《深入理解計算機系統》從程序員的視角詳細闡述計算機系統的本質概念,并展示這些概念如何實實在在地影響應用程序的正確性、性能和實用性。全書共12章,主要內容包括信息的表示和處理、程序的機器級表示、處理器體系結構、優化程序性能、存儲器層次結構、鏈接、異常控制流、虛擬存儲器、系統級I/O、網絡編程、并發編程等。書中提供子大量的例子和練習題,并給出部分答案,有助于讀者加深對正文所述概念和知識的理解。

更多計算機寶庫...

燃烧吧足球登陆