從零開始學算法：十種排序算法介紹

從零開始學算法：十種排序算法介紹（上）占ProgramImpossibleI2007-03-3123:231」17CommentsI本文內(nèi)容遵從CC版權協(xié)議轉(zhuǎn)載請注明出自今天我正式開始按照我的目錄寫我的OI心得了。我要把我所有學到的OI知識傳給以后千千萬萬的OIer。以前寫過的一些東西不重復寫了，但我最后將會重新整理，使之成為一個完整的教程。按照我的目錄，講任何東西之前我都會先介紹時間復雜度的相關知識，以后動不動就會扯到這個東西。這個已經(jīng)寫過了，你可以在這里看到那篇又臭又長的文章。在講排序算法的過程中，我們將始終圍繞時間復雜度的內(nèi)容進行說明。我把這篇文章稱之為“從零開始學算法”，因為排序算法是最基礎的算法，介紹算法時從各種排序算法入手是最好不過的了。給出n個數(shù)，怎樣將它們從小到大排序？下面一口氣講三種常用的算法，它們是最簡單的、最顯然的、最容易想到的。選擇排序（SelectionSort）是說，每次從數(shù)列中找出一個最小的數(shù)放到最前面來，再從剩下的n-1個數(shù)中選擇一個最小的，不斷做下去。插入排序（InsertionSort）是，每次從數(shù)列中取一個還沒有取出過的數(shù)，并按照大小關系插入到已經(jīng)取出的數(shù)中使得已經(jīng)取出的數(shù)仍然有序。冒泡排序（BubbleSort）分為若干趟進行，每一趟排序從前往后比較每兩個相鄰的元素的大?。ㄒ虼艘惶伺判蛞容^n-1對位置相鄰的數(shù)）并在每次發(fā)現(xiàn)前面的那個數(shù)比緊接它后的數(shù)大時交換位置；進行足夠多趟直到某一趟跑完后發(fā)現(xiàn)這一趟沒有進行任何交換操作（最壞情況下要跑n-1趟，這種情況在最小的數(shù)位于給定數(shù)列的最后面時發(fā)生）。事實上，在第一趟冒泡結束后，最后面那個數(shù)肯定是最大的了，于是第二次只需要對前面n-1個數(shù)排序，這又將把這n-1個數(shù)中最小的數(shù)放到整個數(shù)列的倒數(shù)第二個位置。這樣下去，冒泡排序第i趟結束后后面i個數(shù)都已經(jīng)到位了，第i+1趟實際上只考慮前n-i個數(shù)（需要的比較次數(shù)比前面所說的n-1要小）。這相當于用數(shù)學歸納法證明了冒泡排序的正確性：實質(zhì)與選擇排序相同。上面的三個算法描述可能有點模糊了，沒明白的話網(wǎng)上找資料，代碼和動畫演示遍地都是。31415927[3]1415927X[1 3]41 5 9 2 7[1 31415927[3]1415927X[1 3]41 5 9 2 7[1 34]1 5 9 2 7[1 134] 5 9 2 7I[11345]927[1[1[13459]23452723453141592654XX7^4.131452654[9]XXX11342554[69]XX1132454[569]112344[5569]11234[45569]冒泡排序插入排序冒泡排序這三種算法非常容易理解，因為我們生活當中經(jīng)常在用。比如，班上的MM搞選美活動，有人叫我給所有MM排個名。我們通常會用選擇排序，即先找出自己認為最漂亮的，然后找第二漂亮的，然后找第三漂亮的，不斷找剩下的人中最滿意的。打撲克牌時我們希望抓完牌后手上的牌是有序的，三個8挨在一起，后面緊接著兩個9。這時，我們會使用插入排序，每次拿到一張牌后把它插入到手上的牌中適當?shù)奈恢谩Ｊ裁磿r候我們會用冒泡排序呢？比如，體育課上從矮到高排隊時，站隊完畢后總會有人出來，比較挨著的兩個人的身高，指揮到：你們倆調(diào)換一下，你們倆換一下。這是很有啟發(fā)性的。這告訴我們，什么時候用什么排序最好。當人們渴望先知道排在前面的是誰時，我們用選擇排序；當我們不斷拿到新的數(shù)并想保持已有的數(shù)始終有序時，我們用插入排序；當給出的數(shù)列已經(jīng)比較有序，只需要小幅度的調(diào)整一下時，我們用冒泡排序。我們來算一下最壞情況下三種算法各需要多少次比較和賦值操作。選擇排序在第i次選擇時賦值和比較都需要n-i次（在n-i+1個數(shù)中選一個出來作為當前最小值，其余n-i個數(shù)與當前最小值比較并不斷更新當前最小值），然后需要一次賦值操作?？偣残枰猲（n-1）/2次比較與n（n-1）/2+n次賦值。插入排序在第i次尋找插入位置時需要最多i-1次比較（從后往前找到第一個比待插入的數(shù)小的數(shù)，最壞情況發(fā)生在這個數(shù)是所有已經(jīng)取出的數(shù)中最小的一個的時候），在已有數(shù)列中給新的數(shù)騰出位置需要i-1次賦值操作來實現(xiàn)，還需要兩次賦值借助臨時變量把新取出的數(shù)搬進搬出。也就是說，最壞情況下比較需要n（n-1）/2次，賦值需要n（n-1）/2+2n次。我這么寫有點誤導人，大家不要以為程序的實現(xiàn)用了兩個數(shù)組哦，其實一個數(shù)組就夠了，看看上面的演示就知道了。我只說算法，一般不寫如何實現(xiàn)。學算法的都是強人，知道算法了都能寫出一個漂亮的代碼來。冒泡排序第i趟排序需要比較n-i次，n-1趟排序總共n（n-1）/2次。給出的序列逆序排列是最壞的情況，這時每一次比較都要進行交換操作。一次交換操作需要3次賦值實現(xiàn)，因此冒泡排序最壞情況下需要賦值3n（n-1）/2次。按照漸進復雜度理論，忽略所有的常數(shù)，三種排序的最壞情況下復雜度都是一樣的：0（矽2）。但實際應用中三種排序的效率并不相同。實踐證明（政治考試時每道大題都要用這四個字），插入排序是最快的（雖然最壞情況下與選擇排序相當甚至更糟），因為每一次插入時尋找插入的位置多數(shù)情況只需要與已有數(shù)的一部分進行比較（你可能知道這還能二分）。你或許會說冒泡排序也可以在半路上完成，還沒有跑到第n-1趟就已經(jīng)有序。但冒泡排序的交換操作更費時，而插入排序中找到了插入的位置后移動操作只需要用賦值就能完成（你可能知道這還能用move）。本文后面將介紹的一種算法就利用插入排序的這些優(yōu)勢。我們證明了，三種排序方法在最壞情況下時間復雜度都是0（矽2）。但大家想過嗎，這只是最壞情況下的。在很多時候，復雜度沒有這么大，因為插入和冒泡在數(shù)列已經(jīng)比較有序的情況下需要的操作遠遠低于矽2次（最好情況下甚至是線性的）。拋開選擇排序不說（因為它的復雜度是'死”的，對于選擇排序沒有什么“好”的情況），我們下面探討插入排序和冒泡排序在特定數(shù)據(jù)和平均情況下的復雜度。你會發(fā)現(xiàn)，如果把插入排序中的移動賦值操作看作是把當前取出的元素與前面取出的且比它大的數(shù)逐一交換，那插入排序和冒泡排序?qū)?shù)據(jù)的變動其實都是相鄰元素的交換操作。下面我們說明，若只能對數(shù)列中相鄰的數(shù)進行交換操作，如何計算使得n個數(shù)變得有序最少需要的交換次數(shù)。我們定義逆序?qū)Φ母拍?。假設我們要把數(shù)列從小到大排序，一個逆序?qū)κ侵傅脑谠瓟?shù)列中，左邊的某個數(shù)比右邊的大。也就是說，如果找到了某個i和j使得i<j且Ai>Aj，我們就說我們找到了一個逆序?qū)?。比如說，數(shù)列3,1,4,2中有三個逆序?qū)Γ粋€已經(jīng)有序的數(shù)列逆序?qū)€數(shù)為0。我們發(fā)現(xiàn)，交換兩個相鄰的數(shù)最多消除一個逆序?qū)Γ颐芭菖判颍ɑ虿迦肱判颍┲械囊淮谓粨Q恰好能消除一個逆序?qū)?。那么顯然，原數(shù)列中有多少個逆序?qū)γ芭菖判颍ɑ虿迦肱判颍┚托枰嗌俅谓粨Q操作，這個操作次數(shù)不可能再少。若給出的n個數(shù)中有m個逆序?qū)?，插入排序的時間復雜度可以說是O（m+n）的，而冒泡排序不能這么說，因為冒泡排序有很多“無用”的比較（比較后沒有交換），這些無用的比較超過了O（m+n）個。從這個意義上說，插入排序仍然更為優(yōu)秀，因為冒泡排序的復雜度要受到它跑的趟數(shù)的制約。一個典型的例子是這樣的數(shù)列：8,2,3,4,5,6,7,1。在這樣的輸入數(shù)據(jù)下插入排序的優(yōu)勢非常明顯，冒泡排序只能哭著喊上天不公。然而，我們并不想計算排序算法對于某個特定數(shù)據(jù)的效率。我們真正關心的是，對于所有可能出現(xiàn)的數(shù)據(jù)，算法的平均復雜度是多少。不用激動了，平均復雜度并不會低于平方。下面證明，兩種算法的平均復雜度仍然是O（nA2）的。我們僅僅證明算法需要的交換次數(shù)平均為0（矽2）就足夠了。前面已經(jīng)說過，它們需要的交換次數(shù)與逆序?qū)Φ膫€數(shù)相同。我們將證明，n個數(shù)的數(shù)列中逆序?qū)€數(shù)平均0（矽2）個。計算的方法是十分巧妙的。如果把給出的數(shù)列反過來（從后往前倒過來寫），你會發(fā)現(xiàn)原來的逆序?qū)ΜF(xiàn)在變成順序的了，而原來所有的非逆序?qū)ΜF(xiàn)在都成逆序了。正反兩個數(shù)列的逆序?qū)€數(shù)加起來正好就是數(shù)列所有數(shù)對的個數(shù)，它等于n（n-1）/2。于是，平均每個數(shù)列有n（n-1）/4個逆序?qū)?。忽略常?shù)，逆序?qū)ζ骄鶄€數(shù)0"2）。上面的討論啟示我們，要想搞出一個復雜度低于平方級別的排序算法，我們需要想辦法能把離得老遠的兩個數(shù)進行操作。人們想啊想啊想啊，怎么都想不出怎樣才能搞出復雜度低于平方的算法。后來，英雄出現(xiàn)了，DonaldShell發(fā)明了一種新的算法，我們將證明它的復雜度最壞情況下也沒有0（矽2）（似乎有人不喜歡研究正確性和復雜度的證明，我會用實例告訴大家，這些證明是非常有意思的)。他把這種算法叫做Shell增量排序算法(大家常說的希爾排序)。Shell排序算法依賴一種稱之為“排序增量”的數(shù)列，不同的增量將導致不同的效率。假如我們對20個數(shù)進行排序，使用的增量為1,3,7。那么，我們首先對這20個數(shù)進行“7-排序”(7-sortedness)。所謂7-排序，就是按照位置除以7的余數(shù)分組進行排序。具體地說，我們將把在1、8、15三個位置上的數(shù)進行排序，將第2、9、16個數(shù)進行排序，依此類推。這樣，對于任意一個數(shù)字k，單看A(k),A(k+7),A(k+14),..這些數(shù)是有序的。7-排序后，我們接著又進行一趟3-排序(別忘了我們使用的排序增量為1,3,7)。最后進行1-排序(即普通的排序)后整個Shell算法完成?？纯次覀兊睦樱?7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2 <--原數(shù)列33 2 0 5 1 5 7 4 4 0 6 1 6 8 7 9 9 8 2 <-- 7-排序后00 1 1 2 2 3 3 4 4 5 6 5 6 8 7 7 9 8 9 <-- 3-排序后00 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 <-- 1-排序后(完成)在每一趟、每一組的排序中我們總是使用插入排序。仔細觀察上面的例子你會發(fā)現(xiàn)是什么導致7Shell排序的高效。對，每一趟排序?qū)⑹沟脭?shù)列部分有序，從而使得以后的插入排序很快找到插入位置。我們下面將緊緊圍繞這一點來證明Shell排序算法的時間復雜度上界。只要排序增量的第一個數(shù)是1，Shell排序算法就是正確的。但是不同的增量將導致不同的時間復雜度。我們上面例子中的增量(1,3,7,15,31,...,2^k-1)是使用最廣泛的增量序列之一，可以證明使用這個增量的時間復雜度為O(nVn)。這個證明很簡單，大家可以參看一些其它的資料，我們今天不證明它。今天我們證明，使用增量1,2,3,4,6,8,9,12,16,...,2Ap*3Aq，時間復雜度為O(n*(logn)A2)o很顯然，任何一個大于1的正整數(shù)都可以表示為2x+3y，其中x和y是非負整數(shù)。于是，如果一個數(shù)列已經(jīng)是2-排序的且是3-排序的，那么對于此時數(shù)列中的每一個數(shù)A(i)，它的左邊比它大的只有可能是A(i-1)oA2絕對不可能比A12大，因為10可以表示為兩個2和兩個3的和，則A2<A4<A6<A9<A12o那么，在這個增量中的1-排序時每個數(shù)找插入位置只需要比較一次。一共有n個數(shù)，所以1-排序是O(n)的。事實上，這個增量中的2-排序也是O(n)，因為在2-排序之前，這個數(shù)列已經(jīng)是4-排序且6-排序過的，只看數(shù)列的奇數(shù)項或者偶數(shù)項(即單看每一組)的話就又成了剛才的樣子。這個增量序列巧妙就巧妙在，如果我們要進行h-排序，那么它一定是2h-排序過且3h-排序過，于是處理每個數(shù)A(i)的插入時就只需要和A(i-h)進行比較。這個結論對于最開始幾次(h值較大時)的h-排序同樣成立，當2h、3h大于n時，按照定義，我們也可以認為數(shù)列是2h-排序和3h-排序的，這并不影響上述結論的正確性(你也可以認為h太大以致于排序時每一組里的數(shù)字不超過3個，屬于常數(shù)級)?，F(xiàn)在，這個增量中的每一趟排序都是O(n)的，我們只需要數(shù)一下一共跑了多少趟。也就是說，我們現(xiàn)在只需要知道小于n的數(shù)中有多少個數(shù)具有2Ap*3Aq的形式。要想2Ap*3Aq不超過n，p的取值最多O(logn)個，q的取值最多也是O(logn)個，兩兩組合的話共有O(logn*logn)種情況。于是，這樣的增量排序需要跑O((logn)A2)趟，每一趟的復雜度O(n)，總的復雜度為O(n*(logn)A2)。早就說過了，證明時間復雜度其實很有意思。我們自然會想，有沒有能使復雜度降到O(nlogn)甚至更低的增量序列。很遺憾，現(xiàn)在沒有任何跡象表明存在O(nlogn)的增量排序。但事實上，很多時候Shell排序的實際效率超過了O(nlogn)的排序算法。后面我們將介紹三種O(nlogn)的排序算法和三種線性時間的排序算法。最后我們將以外部排序和排序網(wǎng)絡結束這一章節(jié)。彳艮多人問到我關于轉(zhuǎn)貼的問題。我歡迎除商業(yè)目的外任何形式的轉(zhuǎn)貼(論壇、Blog、Wiki、個人網(wǎng)站、PodCast，甚至做成ppt、pdf)，但一定要注明出處，最好保留原始鏈接。我的網(wǎng)站需要點反向鏈接才能在網(wǎng)絡中生存下去，大家也都可以關注并且推廣這個Blogo我一直支持cc版權協(xié)議，因此發(fā)現(xiàn)了文章中的問題或者想要補充什么東西盡管提出來，好讓更多的人學習到好東西。我昨天看Blog上原來寫的一些東西，居然連著發(fā)現(xiàn)了幾個錯誤式子和錯別字，好奇大家居然沒有提出來。發(fā)現(xiàn)了問題真的要告訴我，即使格式有點問題也要說一下，決不能讓它那么錯著。另外有什么建議或想法也請說一下，我希望聽到不同的聲音不同的見解，好讓我決定這類文章以后的發(fā)展方向。

本文被華麗的分割線分為了四段。對于O(nlogn)的排序算法，我們詳細介紹歸并排序并證明歸并排序的時間復雜度，然后簡單介紹堆排序，之后給出快速排序的基本思想和復雜度證明。最后我們將證明，O(nlogn)在理論上已經(jīng)達到了最優(yōu)。學過OI的人一般都學過這些很基礎的東西，大多數(shù)OIer們不必看了。為了保持系列文章的完整性，我還是花時間寫了一下。首先考慮一個簡單的問題：如何在線性的時間內(nèi)將兩個有序隊列合并為一個有序隊列(并輸出)？A隊列：13579B隊列：12789看上面的例子，AB兩個序列都是已經(jīng)有序的了。在給出數(shù)據(jù)已經(jīng)有序的情況下，我們會發(fā)現(xiàn)很多神奇的事，比如，我們將要輸出的第一個數(shù)一定來自于這兩個序列各自最前面的那個數(shù)。兩個數(shù)都是1，那么我們隨便取出一個(比如A隊列的那個1)并輸出：A隊列：13579B隊列：12789輸出：1注意，我們?nèi)〕隽艘粋€數(shù)，在原數(shù)列中刪除這個數(shù)。刪除操作是通過移動隊首指針實現(xiàn)的，否則復雜度就高了。現(xiàn)在，A隊列打頭的數(shù)變成3了，B隊列的隊首仍然是1。此時，我們再比較3和1哪個大并輸出小的那個數(shù)：A隊列：13579B隊列：12789輸出：11接下來的幾步如下：A隊列：13579BA隊列：13579B隊列：42789 ==>輸出：112A隊列：I579B隊列：1-2789 ==>輸出：1123A隊列：I■與79B隊列：1-2789 ==>輸出：11235A隊列：13579B隊列：1-2789 -輸出：112357我希望你明白了這是怎么做的。這個做法顯然是正確的，復雜度顯然是線性。歸并排序(Merge$函)將會用到上面所說的合并操作。給出一個數(shù)列，歸并排序利用合并操作在O(nlogn)的時間內(nèi)將數(shù)列從小到大排序。歸并排序用的是分治(DivideandConquer)的思想。首先我們把給出的數(shù)列平分為左右兩段，然后對兩段數(shù)列分別進行排序，最后用剛才的合并算法把這兩段(已經(jīng)排過序的)數(shù)列合并為一個數(shù)列。有人會問“對左右兩段數(shù)列分別排序時用的什么排序”么？答案是：用歸并排序。也就是說，我們遞歸地把每一段數(shù)列又分成兩段進行上述操作。你不需要關心實際上是怎么操作的，我們的程序代碼將遞歸調(diào)用該過程直到數(shù)列不能再分(只有一個數(shù))為止。初看這個算法時有人會誤以為時間復雜度相當高。我們下面給出的一個圖將用非遞歸的眼光來看歸并排序的實際操作過程，供大家參考。我們可以借助這個圖證明，歸并排序算法的時間復雜度為O(nlogn)。TOC\o"1-5"\h\z[3][1] [4] [1] [5] [9] [2] [7]\/ \ / \ / \ /[13] [1 4] [5 9] [2 7]\ / \ /[1134] [2579]\ /[11234579]上圖中的每一個“\/”表示的是上文所述的線性時間合并操作。上圖用了4行來圖解歸并排序。如果有n個數(shù)，表示成上圖顯然需要O(logn)行。每一行的合并操作復雜度總和都是O(n)，那么logn行的總復雜度為O(nlogn)。這相當于用遞歸樹的方法對歸并排序的復雜度進行了分析。假設，歸并排序的復雜度為T(n)，T(n)由兩個T(n/2)和一個關于n的線性時間組成，那么T(n)=2*T(n/2)+O(n)。不斷展開這個式子我們可以同樣可以得到T(n)=O(nlogn)的結論，你可以自己試試。如果你能在線性的時間里把分別計算出的兩組不同數(shù)據(jù)的結果合并在一起，根據(jù)T(n)=2*T(n/2)+O(n)=O(nlogn)，那么我們就可以構造O(nlogn)的分治算法。這個結論后面經(jīng)常用。我們將在計算幾何部分舉一大堆類似的例子。如果你第一次見到這么詭異的算法，你可能會對這個感興趣。分治是遞歸的一種應用。這是我們第一次接觸遞歸運算。下面說的快速排序也是用的遞歸的思想。遞歸程序的復雜度分析通常和上面一樣，主定理(MasterTheory)可以簡化這個分析過程。主定理和本文內(nèi)容離得太遠，我們以后也不會用它，因此我們不介紹它，大家可以自己去查。有個名詞在這里的話找學習資料將變得非常容易，我最怕的就是一個東西不知道叫什么名字，半天找不到資料。歸并排序有一個有趣的副產(chǎn)品。利用歸并排序能夠在O(nlogn)的時間里計算出給定序列里逆序?qū)Φ膫€數(shù)。你可以用任何一種平衡二叉樹來完成這個操作，但用歸并排序統(tǒng)計逆序?qū)Ω奖?。我們討論逆序?qū)σ话闶钦f的一個排列中的逆序?qū)?，因此這里我們假設所有數(shù)不相同。假如我們想要數(shù)1,6,3,2,5,4中有多少個逆序?qū)?，我們首先把這個數(shù)列分為左右兩段。那么一個逆序?qū)χ豢赡苡腥N情況：兩個數(shù)都在左邊，兩個數(shù)都在右邊，一個在左一個在右。在左右兩段分別處理完后，線性合并的過程中我們可以順便算出所有第三種情況的逆序?qū)τ卸嗌賯€。換句話說，我們能在線性的時間里統(tǒng)計出A隊列的某個數(shù)比B隊列的某個數(shù)大有多少種情況。A隊列：136 A隊列：136 A隊列：136 A隊列：I6 A隊列：I6B隊列：245==> B隊列：245 ==> B隊列：245 ==> B隊列：245 ==> B隊列：245 ……輸出： 輸出：1 輸出：12 輸出：123 輸出：1234每一次從B隊列取出一個數(shù)時，我們就知道了在A隊列中有多少個數(shù)比B隊列的這個數(shù)大，它等于A隊列現(xiàn)在還剩的數(shù)的個數(shù)。比如，當我們從B隊列中取出2時，我們同時知道了A隊列的3和6兩個數(shù)比2大。在合并操作中我們不斷更新A隊列中還剩幾個數(shù)，在每次從B隊列中取出一個數(shù)時把當前A隊列剩的數(shù)目加進最終答案里。這樣我們算出了所有“大的數(shù)在前一半，小的數(shù)在后一半”的情況，其余情況下的逆序?qū)υ谶@之前已經(jīng)被遞歸地算過了。====================華麗的分割線==================堆排序(HeapSort)利用了堆(Heap)這種數(shù)據(jù)結構(什么是堆？)。堆的插入操作是平均常數(shù)的，而刪除一個根節(jié)點需要花費O(logn)的時間。因此，完成堆排序需要線性時間建立堆(把所有元素依次插入一個堆)，然后用總共O(nlogn)的時間不斷取出最小的那個數(shù)。只要堆會搞，堆排序就會搞。堆在那篇日志里有詳細的說明，因此這里不重復說了。============================華麗的分割線============================快速排序(QuickSort)也應用了遞歸的思想。我們想要把給定序列分成兩段，并對這兩段分別進行排序。一種不錯的想法是，選取一個數(shù)作為“關鍵字”，并把其它數(shù)分割為兩部分，把所有小于關鍵字的數(shù)都放在關鍵字的左邊，大于關鍵字的都放在右邊，然后遞歸地對左邊和右邊進行排序。把該區(qū)間內(nèi)的所有數(shù)依次與關鍵字比較，我們就可以在線性的時間里完成分割的操作。完成分割操作有很多有技巧性的實現(xiàn)方法，比如最常用的一種是定義兩個指針，一個從前往后找找到比關鍵字大的，一個從后往前找到比關鍵字小的，然后兩個指針對應的元素交換位置并繼續(xù)移動指針重復剛才的過程。這只是大致的方法，具體的實現(xiàn)還有很多細節(jié)問題?？焖倥判蚴俏覀冏畛Ｓ玫拇a之一，網(wǎng)上的快速排序代碼五花八門，各種語言，各種風格的都有。大家可以隨便找一個來看看，我說過了我們講算法但不講如何實現(xiàn)°NOIp很簡單，很多人NOIp前就背了一個快速排序代碼就上戰(zhàn)場了。當時我把快速排序背完了，抓緊時間還順便背了一下歷史，免得晚上聽寫又不及格。不像歸并排序，快速排序的時間復雜度很難計算。我們可以看到，歸并排序的復雜度最壞情況下也是O(nlogn)的，而快速排序的最壞情況是0(矽2)的。如果每一次選的關鍵字都是當前區(qū)間里最大(或最小)的數(shù)，那么這樣將使得每一次的規(guī)模只減小一個數(shù)，這和插入排序、選擇排序等平方級排序沒有區(qū)別。這種情況不是不可能發(fā)生。如果你每次選擇關鍵字都是選擇的該區(qū)間的第一個數(shù)，而給你的數(shù)據(jù)恰好又是已經(jīng)有序的，那你的快速排序就完蛋了。顯然，最好情況是每一次選的數(shù)正好就是中位數(shù)，這將把該區(qū)間平分為兩段，復雜度和前面討論的歸并排序一模一樣。根據(jù)這一點，快速排序有一些常用的優(yōu)化。比如，我們經(jīng)常從數(shù)列中隨機取一個數(shù)當作是關鍵字(而不是每次總是取固定位置上的數(shù))，從而盡可能避免某些特殊的數(shù)據(jù)所導致的低效。更好的做法是隨機取三個數(shù)并選擇這三個數(shù)的中位數(shù)作為關鍵字。而對三個數(shù)的隨機取值反而將花費更多的時間，因此我們的這三個數(shù)可以分別取數(shù)列的頭一個數(shù)、末一個數(shù)和正中間那個數(shù)。另外，當遞歸到了一定深度發(fā)現(xiàn)當前區(qū)間里的數(shù)只有幾個或十幾個時，繼續(xù)遞歸下去反而費時，不如返回插入排序后的結果。這種方法同時避免了當數(shù)字太少時遞歸操作出錯的可能。下面我們證明，快速排序算法的平均復雜度為O(nlogn)。不同的書上有不同的解釋方法，這里我選用算法導論上的講法。它更有技巧性一些，更有趣一些，需要轉(zhuǎn)幾個彎才能想明白。看一看快速排序的代碼。正如我們提到過的那種分割方法，程序在經(jīng)過若干次與關鍵字的比較后才進行一次交換，因此比較的次數(shù)比交換次數(shù)更多。我們通過證明一次快速排序中元素之間的比較次數(shù)平均為O(nlogn)來說明快速排序算法的平均復雜度。證明的關鍵在于，我們需要算出某兩個元素在整個算法過程中進行過比較的概率。我們舉一個例子。假如給出了1到10這10個數(shù)，第一次選擇關鍵字7將它們分成了｛1,2,3,4,5,6｝和｛8,9,10｝兩部分，遞歸左邊時我們選擇了3作為關鍵字，使得左部分又被分割為｛1,2｝和｛4,5,6｝。我們看到，數(shù)字7與其它所有數(shù)都比較過一次，這樣才能實現(xiàn)分割操作。同樣地，1到6這6個數(shù)都需要與3進行一次比較(除了它本身之外)。然而，3和9決不可能相互比較過，2和6也不可能進行過比較，因為第一次出現(xiàn)在3和9,2和6之間的關鍵字把它們分割開了。也就是說，兩個數(shù)A(i)和A(j)比較過，當且僅當?shù)谝粋€滿足A(i)<=x<=A(j)的關鍵字x恰好就是A(i)或A(j)(假設A(i)比A(j)小)。我們稱排序后第i小的數(shù)為Z(i)，假設i<j，那么第一次出現(xiàn)在Z(i)和Z(j)之間的關鍵字恰好就是Z(i)或Z(j)的概率為2/(j-i+1)，這是因為當Z(i)和Z(j)之間還不曾有過關鍵字時，Z(i)和Z(j)處于同一個待分割的區(qū)間，不管這個區(qū)間有多大，不管遞歸到哪里了，關鍵字的選擇總是隨機的。我們得到，Z(i)和Z(j)在一次快速排序中曾經(jīng)比較過的概率為2/(j-i+1)?，F(xiàn)在有四個數(shù)，2,3,5,7。排序時，相鄰的兩個數(shù)肯定都被比較過，2和5、3和7都有2/3的概率被比較過，2和7之間被比較過有2/4的可能。也就是說，如果對這四個數(shù)做12次快速排序，那么2和3、3和5、5和7之間一共比較了12*3=36次，2和5、3和7之間總共比較了8*2=16次，2和7之間平均比較了6次。那么，12次排序中總的比較次數(shù)期望值為36+16+6=58。我們可以計算出單次的快速排序平均比較了多少次：58/12=29/6。其實，它就等于6項概率之和，1+1+1+2/3+2/3+2/4=29/6。這其實是與期望值相關的一個公式。同樣地，如果有n個數(shù)，那么快速排序平均需要的比較次數(shù)可以寫成下面的式子。令k=j-i，我們能夠最終得到比較次數(shù)的期望值為O(nlogn)。n-1m nZS1?TT7T1=1j=l+lnn-1n-i打n-lm今<zsli=li=ln-1二￡O(lagn)i=l=O(nlogn)這里用到了一個知識：1+1/2+1/3+...+1/n與logn增長速度相同，即S(1/n)=0(logn)。它的證明放在本文的最后。在三種O(nlogn)的排序算法中，快速排序的理論復雜度最不理想，除了它以外今天說的另外兩種算法都是以最壞情況O(nlogn)的復雜度進行排序。但實踐上看快速排序效率最高(不然為啥叫快速排序呢)原因在于快速排序的代碼比其它同復雜度的算法更簡潔，常數(shù)時間更小?？焖倥判蛞灿幸粋€有趣的副產(chǎn)品：快速選擇給出的一些數(shù)中第k小的數(shù)。一種簡單的方法是使用上述任一種O(nlogn)的算法對這些數(shù)進行排序并返回排序后數(shù)組的第k個元素。快速選擇(QuickSelect)算法可以在平均O(n)的時間完成這一操作。它的最壞情況同快速排序一樣，也是0"2)。在每一次分割后，我們都可以知道比關鍵字小的數(shù)有多少個，從而確定了關鍵字在所有數(shù)中是第幾小的。我們假設關鍵字是第m小。如果k=m，那么我們就找到了答案——第k小元素即該關鍵字。否則，我們遞歸地計算左邊或者右邊：當k<m時，我們遞歸地尋找左邊的元素中第k小的；當k>m時，我們遞歸地尋找右邊的元素中第k-m小的數(shù)。由于我們不考慮所有的數(shù)的順序，只需要遞歸其中的一邊，因此復雜度大大降低。復雜度平均線性，我們不再具體證了。還有一種算法可以在最壞O(n)的時間里找出第k小元素。那是我見過的所有算法中最沒有實用價值的算法。那個O(n)只有理論價值。====================華麗的分割線==================我們前面證明過，僅僅依靠交換相鄰元素的操作，復雜度只能達到O(M2)。于是，人們嘗試交換距離更遠的元素。當人們發(fā)現(xiàn)O(nlogn)的排序算法似乎已經(jīng)是極限的時候，又是什么制約了復雜度的下界呢？我們將要討論的是更底層的東西。我們?nèi)匀患僭O所有的數(shù)都不相等。我們總是不斷在數(shù)與數(shù)之間進行比較。你可以試試，只用4次比較絕對不可能給4個數(shù)排出順序。每多進行一次比較我們就又多知道了一個大小關系，從4次比較中一共可以獲知4個大小關系。4個大小關系共有2人4=16種組合方式，而4個數(shù)的順序一共有4!=24種。也就是說，4次比較可能出現(xiàn)的結果數(shù)目不足以區(qū)分24種可能的順序。更一般地，給你n個數(shù)叫你排序，可能的答案共有n!個，k次比較只能區(qū)分2V種可能，于是只有2V>=n!時才有可能排出順序。等號兩邊取對數(shù)，于是，給n個數(shù)排序至少需要log2(n!)次。注意，我們并沒有說明一定能通過log2(n!)次比較排出順序。雖然2人5=32超過了4!，但這不足以說明5次比較一定足夠。如何用5次比較確定4個數(shù)的大小關系還需要進一步研究。第一次例外發(fā)生在n=12的時候，雖然2人29>12!，但現(xiàn)已證明給12個數(shù)排序最少需要30次比較。我們可以證明log(n!)的增長速度與nlogn相同，即log(n!)=0(nlogn)o這是排序所需要的最少的比較次數(shù)，它給出了排序復雜度的一個下界。log(n!)=O(nlogn)的證明也附在本文最后。這篇日志的第三題中證明log2(N)是最優(yōu)時用到了幾乎相同的方法。那種“用天平稱出重量不同的那個球至少要稱幾次”一類題目也可以用這種方法來解決。事實上，這里有一整套的理論，它叫做信息論。信息論是由香農(nóng)(Shannon)提出的。他用對數(shù)來表示信息量，用熵來表示可能的情況的隨機性，通過運算可以知道你目前得到的信息能夠怎樣影響最終結果的確定。如果我們的信息量是以2為底的，那信息論就變成信息學了。從根本上說，計算機的一切信息就是以2為底的信息量(bits=binarydigits)，因此我們常說香農(nóng)是數(shù)字通信之父。信息論和熱力學關系密切，比如熵的概念是直接從熱力學的熵定義引申過來的。和這個有關的東西已經(jīng)嚴重偏題了，這里不說了，有興趣可以去看《信息論與編碼理論》。我對這個也很有興趣，半懂不懂的，很想了解更多的東西，有興趣的同志不妨加入討論。物理學真的很神奇，利用物理學可以解決很多純數(shù)學問題，我有時間的話可以舉一些例子。我他媽的為啥要選文科呢。后面將介紹的三種排序是線性時間復雜度，因為，它們排序時根本不是通過互相比較來確定大小關系的。附1：S(1/n)=0(logn)的證明首先我們證明，S(1/n)=O(logn)。在式子1+1/2+1/3+1/4+1/5+...中，我們把1/3變成1/2，使得兩個1/2加起來湊成一個1；再把1/5,1/6和1/7全部變成1/4，這樣四個1/4加起來又是一個1。我們把所有1/2Ak的后面2Ak-1項全部擴大為1/2^k，使得這2^k個分式加起來是一個1?，F(xiàn)在，1+1/2+...+1/n里面產(chǎn)生了幾個1呢？我們只需要看小于n的數(shù)有多少個2的冪即可。顯然，經(jīng)過數(shù)的擴大后原式各項總和為logn。O(logn)是S(1/n)的復雜度上界。然后我們證明，Z(1/n)=Q(logn)。在式子1+1/2+1/3+1/4+1/5+...中，我們把1/3變成1/4，使得兩個1/4加起來湊成一個1/2；再把1/5,1/6和1/7全部變成1/8，這樣四個1/8加起來又是一個1/2。我們把所有1/2V的前面2V-1項全部縮小為1/2V，使得這2V個分式加起來是一個1/2?，F(xiàn)在，1+1/2+...+1/n里面產(chǎn)生了幾個1/2呢？我們只需要看小于n的數(shù)有多少個2的冪即可。顯然，經(jīng)過數(shù)的縮小后原式各項總和為1/2*logn。Q(logn)是S(1/n)的復雜度下界。附2：log(n!)=0(nlogn)的證明首先我們證明，log(n!)=O(nlogn)。顯然n!<nAn，兩邊取對數(shù)我們得到log(n!)vlog(Mn)，而log(nAn)就等于nlogn。因此，O(nlogn)是log(n!)的復雜度上界。然后我們證明，log(n!)=Q(nlogn)。n!=n(n-1)(n-2)(n-3)....1，把前面一半的因子全部縮小到n/2,后面一半因子全部舍去，顯然有n!>(n/2)A(n/2)。兩邊取對數(shù)，log(n!)>(n/2)log(n/2)，后者即Q(nlogn)。因此，Q(nlogn)是log(n!)的復雜度下界。今天寫到這里了，大家?guī)兔πε赌敲?，有什么方法可以不用比較就能排出順序呢？借助Hash表的思想，多數(shù)人都能想出這樣一種排序算法來。我們假設給出的數(shù)字都在一定范圍中，那么我們就可以開一個范圍相同的數(shù)組，記錄這個數(shù)字是否出現(xiàn)過。由于數(shù)字有可能有重復，因此Hash表的概念需要擴展，我們需要把數(shù)組類型改成整型，用來表示每個數(shù)出現(xiàn)的次數(shù)。看這樣一個例子，假如我們要對數(shù)列314159265359進行排序。由于給定數(shù)字每一個都小于10,因此我們開一個0到9的整型數(shù)組T[i]，記錄每一個數(shù)出現(xiàn)了幾次。讀到一個數(shù)字x，就把對應的T[x]加一。A[]=3,1,4,1,5,9,2,6,5,3,5,9+一+——+-一+——一+——+-一+——-+-——+一——+一+數(shù)字i：I0I1I2I3I4I5I6I7I8I9I+一+——+-一+——一+——+-一+——-+-——+一——+一+出現(xiàn)次數(shù)T[i]：I0I2|1I2I1I3I1I0I0I2I+一+——+-一+——一+——+-一+——-+-——+一——+一+最后，我們用一個指針從前往后掃描一遍，按照次序輸曲到9,每個數(shù)出現(xiàn)了幾次就輸出幾個。假如給定的數(shù)是n個大小不超過m的自然數(shù)，顯然這個算法的復雜度是O(m+n)的。我曾經(jīng)以為，這就是線性時間排序了。后來我發(fā)現(xiàn)我錯了。再后來，我發(fā)現(xiàn)我曾犯的錯誤是一個普遍的錯誤。很多人都以為上面的這個算法就是傳說中的計數(shù)排序。問題出在哪里了？為什么它不是線性時間的排序算法？原因是，這個算法根本不是排序算法，它根本沒有對原數(shù)據(jù)進行排序。問題一：為什么說上述算法沒有對數(shù)據(jù)進行排序？STOP!Youshouldthinkforawhile.我們班有很多MM。和身高相差太遠的MM在一起肯定很別扭，接個吻都要彎腰才行(小貓矮死了)。為此，我希望給我們班的MM的身高排序。我們班MM的身高，再離譜也沒有超過2米的，這很適合用我們剛才的算法。我們在黑板上畫一個100到200的數(shù)組，MM依次自曝身高，我負責畫“正”字統(tǒng)計人數(shù)。統(tǒng)計出來了，從小到大依次為141,143,143,147,152,153,...。這算哪門子排序？就一排數(shù)字對我有什么用，我要知道的是哪個MM有多高。我們僅僅把元素的屬性值從小到大列了出來，但我們沒有對元素本身進行排序。也就是說，我們需要知道輸出結果的每個數(shù)值對應原數(shù)據(jù)的哪一個元素。下文提到的“排序算法的穩(wěn)定性”也和屬性值與實際元素的區(qū)別有關。問題二：怎樣將線性時間排序后的輸出結果還原為原數(shù)據(jù)中的元素?STOP!Youshouldthinkforawhile.同樣借助Hash表的思想，我們立即想到了類似于開散列的方法。我們用鏈表把屬性值相同的元素串起來，掛在對應的T[i]上。每次讀到一個數(shù)，在增加T[i]的同時我們把這個元素放進T[i]延伸出去的鏈表里。這樣，輸出結果時我們可以方便地獲得原數(shù)據(jù)中的所有屬性值為i的元素。A[]=3,1,4,1,5,9,2,6,5,3,5,9+一+——+-——+——-+——+--+ + + + +數(shù)字i：I0I1I2I3I4I5I6I7I8I9I+一+——+-——+——-+——+--+ + + + +出現(xiàn)次數(shù)T[i]：I0I2I1I2I1I3I1I0I0I2I+ +o--+-O-+-O-+-Q-+-Q-+一0+ + +-Q-+IIIIII+--++-+IIIIA[1]I+-++---+I IIA[6]A[2]A[7]IA[3]A[5] A[8]IIIIA[12]A[4]A[10]A[9]A[11]形象地說，我們在地上擺10個桶，每個桶編一個號，然后把數(shù)據(jù)分門別類放在自己所屬的桶里。這種排序算法叫做桶式排序(BucketSort)。本文最后你將看到桶式排序的另一個用途。鏈表寫起來比較麻煩，一般我們不使用它。我們有更簡單的方法。問題三：同樣是輸出元素本身，你能想出不用鏈表的其它算法么?STOP!Youshouldthinkforawhile.A[]=3,1,4,1,5,9,2,6,5,3,5,9TOC\o"1-5"\h\z+ 1 1 1 1 1 1 1 1 1 +數(shù)字i： |0|1|2|3|4|5|6|7|8|9|+ 1 1 1 1 1 1 1 1 1 +出現(xiàn)次數(shù)T[i]： | 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 | 0 | 2 |+ 1 1 1 1 1 1 1 1 1 +修改后的T[i]： | 0 | 2 | 3 | 5 | 6 | 9 | 10| 10| 10| 12|+ 1 1 1 1 1 1 1 1 1 +所有數(shù)都讀入后，我們修改T[i]數(shù)組的值，使得T[i]表示數(shù)字i可能的排名的最大值。比如，1最差排名第二，3最遠可以排到第五。T數(shù)組的最后一個數(shù)應該等于輸入數(shù)據(jù)的數(shù)字個數(shù)。修改T數(shù)組的操作可以用一次線性的掃描累加完成。我們還需要準備一個輸出數(shù)組。然后，我們從后往前掃描A數(shù)組，依照T數(shù)組的指示依次把原數(shù)據(jù)的元素直接放到輸出數(shù)組中，同時T[i]的值減一。之所以從后往前掃描A數(shù)組，是因為這樣輸出結果才是穩(wěn)定的。我們說一個排序算法是穩(wěn)定的（Stable），當算法滿足這樣的性質(zhì)：屬性值相同的元素，排序后前后位置不變，本來在前面的現(xiàn)在仍然在前面。不要覺得排序算法是否具有穩(wěn)定性似乎關系不大，排序的穩(wěn)定性在下文的某個問題中將變得非常重要。你可以倒回去看看前面說的七種排序算法哪些是穩(wěn)定的。例子中，A數(shù)組最后一個數(shù)9所對應的T[9]=12，我們直接把9放在待輸出序列中的第12個位置，然后T[9]變成11（這樣下一次再出現(xiàn)9時就應該放在第11位）。A[]=3,1,4,1,5,9,2,6,5,3,5,9<--T[i]=0,2,3,5,6,9,10,10,10,11TOC\o"1-5"\h\zAns= 9接下來的幾步如下：A[]=3,1,4,1,5,9,2,6,5,3,5<--T[i]=0,2,3,5,6,8,10,10,10,11Ans= 5 9A[]=3,1,4,1,5,9,2,6,5,3<--T[i]=0,2,3,4,6,8,10,10,10,11Ans= 3 5 9A[]=3,1,4,1,5,9,2,6,5<--T[i]=0,2,3,4,6,7,10,10,10,11Ans= 3__55__9這種算法叫做計數(shù)排序（CountingSort）。正確性和復雜度都是顯然的。問題四：給定數(shù)的數(shù)據(jù)范圍大了該怎么辦？STOP!Youshouldthinkforawhile.前面的算法只有在數(shù)據(jù)的范圍不大時才可行，如果給定的數(shù)在長整范圍內(nèi)的話，這個算法是不可行的，因為你開不下這么大的數(shù)組。Radix排序（RadixSort）解決了這個難題。昨天我沒事翻了一下初中（9班）時的同學錄，回憶了一下過去。我把比較感興趣的MM的生日列在下面（絕對真實）。如果列表中的哪個MM有幸看到了這篇日志（幾乎不可能），左邊的Support欄有我的電子聯(lián)系方式，我想知道你們怎么樣了。排名不分先后。198808181988081619890426198804051989012519881004198812091989012619890228這就是我的數(shù)據(jù)了?，F(xiàn)在，我要給這些數(shù)排序。假如我的電腦只能開H0..99的數(shù)組，那計數(shù)排序算法最多對兩位數(shù)進行排序。我就把每個八位數(shù)兩位兩位地分成四段（圖1），分別進行四次計數(shù)排序。地球人都知道月份相同時應該看哪一日，因此我們看月份的大小時應該事先保證日已經(jīng)有序。換句話說，我們先對“最不重要”的部分進行排序。我們先對所有數(shù)的最后兩位進行一次計數(shù)排序（圖2）。注意觀察1月26號的MM和4月26號的MM，本次排序中它們的屬性值相同，由于計數(shù)排序是穩(wěn)定的，因此4月份那個排完后依然在1月份那個的前頭。接下來我們對百位和千位進行排序（圖3）。你可以看到兩個26日的MM在這一次排序中分出了大小，而月份相同的MM依然保持日數(shù)有序（因為計數(shù)排序是穩(wěn)定的）。最后我們對年份排序（圖4），完成整個算法。大家都是跨世紀的好兒童，因此沒有圖5了。1^00,08,16逐日04lg」□1,2519,SS,04,051^08,08,1619,86,04,0519,69,□119,SS,08,1619,89,04,2619,8642,0919,69,□2,2S19,SS1^88,04,05lg.ss.os,16□4,0519,SS,10,0419,89,01,25lg.ss.os,IS□419,SS,12,091^88,10,04逐甌L25□S19,S9,01,2519,00,12,0919,0^04,2619,00,□S,is19,S9,01,2619,89,01,2619,0^01,2619,00,10,0419,S9,02,2819,89,02,2019,0^02,2319,00,12,0919,S9,04,26匿］1匿］￡匿13［U4這種算法顯然是正確的。它的復雜度一般寫成O（d*（n+m）），其中n表示n個數(shù)，m是我開的數(shù)組大?。ū纠衜=100），d是一個常數(shù)因子（本例中d=4）。我們認為它也是線性的。問題五：這樣的排序方法還有什么致命的缺陷？STOP!Youshouldthinkforawhile.即使數(shù)據(jù)有30位，我們也可以用d=5或6的Radix算法進行排序。但，要是給定的數(shù)據(jù)有無窮多位怎么辦？有人說，這可能么。這是可能的，比如給定的數(shù)