從零開始學(xué)算法：十種排序算法介紹

從零開始學(xué)算法：十種排序算法介紹（中）占ProgramImpossible|52007-04-0613:52|15Comments|本文內(nèi)容遵從CC版權(quán)協(xié)議轉(zhuǎn)載請注明出自本文被華麗的分割線分為了四段。對于O（nlogn）的排序算法，我們詳細(xì)介紹歸并排序并證明歸并排序的時(shí)間復(fù)雜度，然后簡單介紹堆排序，之后給出快速排序的基本思想和復(fù)雜度證明。最后我們將證明，O（nlogn）在理論上已經(jīng)達(dá)到了最優(yōu)。學(xué)過OI的人一般都學(xué)過這些很基礎(chǔ)的東西，大多數(shù)OIer們不必看了。為了保持系列文章的完整性，我還是花時(shí)間寫了一下。首先考慮一個(gè)簡單的問題：如何在線性的時(shí)間內(nèi)將兩個(gè)有序隊(duì)列合并為一個(gè)有序隊(duì)列（并輸出）？A隊(duì)列：13579B隊(duì)列：12789看上面的例子，AB兩個(gè)序列都是已經(jīng)有序的了。在給出數(shù)據(jù)已經(jīng)有序的情況下，我們會(huì)發(fā)現(xiàn)很多神奇的事，比如，我們將要輸出的第一個(gè)數(shù)一定來自于這兩個(gè)序列各自最前面的那個(gè)數(shù)。兩個(gè)數(shù)都是1，那么我們隨便取出一個(gè)（比如A隊(duì)列的那個(gè)1）并輸出：A隊(duì)列：13579B隊(duì)列：12789輸出：1注意，我們?nèi)〕隽艘粋€(gè)數(shù)，在原數(shù)列中刪除這個(gè)數(shù)。刪除操作是通過移動(dòng)隊(duì)首指針實(shí)現(xiàn)的，否則復(fù)雜度就高了?，F(xiàn)在，A隊(duì)列打頭的數(shù)變成3了，B隊(duì)列的隊(duì)首仍然是1。此時(shí)，我們再比較3和1哪個(gè)大并輸出小的那個(gè)數(shù)：A隊(duì)列：13579B隊(duì)列：12789輸出：11接下來的幾步如下：A隊(duì)^0：13579A隊(duì)^0：L3579A隊(duì)列：13579A隊(duì)列：13579B隊(duì)^0：皿789==>B隊(duì)^0：1789==>B隊(duì)^0：皿789==>B隊(duì)列：1_2789??輸出：112?輸出：1123輸出：11235輸出：112357我希望你明白了這是怎么做的。這個(gè)做法顯然是正確的，復(fù)雜度顯然是線性。歸并排序(MergeSort)將會(huì)用到上面所說的合并操作。給出一個(gè)數(shù)列，歸并排序利用合并操作在O(nlogn)的時(shí)間內(nèi)將數(shù)列從小到大排序。歸并排序用的是分治(DivideandConquer)的思想。首先我們把給出的數(shù)列平分為左右兩段，然后對兩段數(shù)列分別進(jìn)行排序，最后用剛才的合并算法把這兩段(已經(jīng)排過序的)數(shù)列合并為一個(gè)數(shù)列。有人會(huì)問“對左右兩段數(shù)列分別排序時(shí)用的什么排序”么？答案是：用歸并排序。也就是說，我們遞歸地把每一段數(shù)列又分成兩段進(jìn)行上述操作。你不需要關(guān)心實(shí)際上是怎么操作的，我們的程序代碼將遞歸調(diào)用該過程直到數(shù)列不能再分(只有一個(gè)數(shù))為止。初看這個(gè)算法時(shí)有人會(huì)誤以為時(shí)間復(fù)雜度相當(dāng)高。我們下面給出的一個(gè)圖將用非遞歸的眼光來看歸并排序的實(shí)際操作過程，供大家參考。我們可以借助這個(gè)圖證明，歸并排序算法的時(shí)間復(fù)雜度為O(nlogn)。[3][1][4][1][5][9][2][7]TOC\o"1-5"\h\z\/\/\/\/[13][14][59][27]\/\/[1134][2579]\/[11234579]上圖中的每一個(gè)“'/”表示的是上文所述的線性時(shí)間合并操作。上圖用了4行來圖解歸并排序。如果有n個(gè)數(shù)，表示成上圖顯然需要O(logn)行。每一行的合并操作復(fù)雜度總和都是O(n)，那么logn行的總復(fù)雜度為O(nlogn)。這相當(dāng)于用遞歸樹的方法對歸并排序的復(fù)雜度進(jìn)行了分析。假設(shè)，歸并排序的復(fù)雜度為T(n)，T(n)由兩個(gè)T(n/2)和一個(gè)關(guān)于n的線性時(shí)間組成，那么T(n)=2*T(n/2)+O(n)。不斷展開這個(gè)式子我們可以同樣可以得到T(n)=O(nlogn)的結(jié)論，你可以自己試試。如果你能在線性的時(shí)間里把分別計(jì)算出的兩組不同數(shù)據(jù)的結(jié)果合并在一起，根據(jù)T(n)=2*T(n/2)+O(n)=O(nlogn)，那么我們就可以構(gòu)造O(nlogn)的分治算法。這個(gè)結(jié)論后面經(jīng)常用。我們將在計(jì)算幾何部分舉一大堆類似的例子。如果你第一次見到這么詭異的算法，你可能會(huì)對這個(gè)感興趣。分治是遞歸的一種應(yīng)用。這是我們第一次接觸遞歸運(yùn)算。下面說的快速排序也是用的遞歸的思想。遞歸程序的復(fù)雜度分析通常和上面一樣，主定理(MasterTheory)可以簡化這個(gè)分析過程。主定理和本文內(nèi)容離得太遠(yuǎn)，我們以后也不會(huì)用它，因此我們不介紹它，大家可以自己去查。有個(gè)名詞在這里的話找學(xué)習(xí)資料將變得非常容易，我最怕的就是一個(gè)東西不知道叫什么名字，半天找不到資料。歸并排序有一個(gè)有趣的副產(chǎn)品。利用歸并排序能夠在O(nlogn)的時(shí)間里計(jì)算出給定序列里逆序?qū)Φ膫€(gè)數(shù)。你可以用任何一種平衡二叉樹來完成這個(gè)操作，但用歸并排序統(tǒng)計(jì)逆序?qū)Ω奖?。我們討論逆序?qū)σ话闶钦f的一個(gè)排列中的逆序?qū)Γ虼诉@里我們假設(shè)所有數(shù)不相同。假如我們想要數(shù)1,6,3,2,5,4中有多少個(gè)逆序?qū)?，我們首先把這個(gè)數(shù)列分為左右兩段。那么一個(gè)逆序?qū)χ豢赡苡腥N情況：兩個(gè)數(shù)都在左邊，兩個(gè)數(shù)都在右邊，一個(gè)在左一個(gè)在右。在左右兩段分別處理完后，線性合并的過程中我們可以順便算出所有第三種情況的逆序?qū)τ卸嗌賯€(gè)。換句話說，我們能在線性的時(shí)間里統(tǒng)計(jì)出A隊(duì)列的某個(gè)數(shù)比B隊(duì)列的某個(gè)數(shù)大有多少種情況。A隊(duì)列：136A隊(duì)列：136A隊(duì)列：136A隊(duì)列:1_36A隊(duì)列：1^6B隊(duì)列：245==>B隊(duì)列：245==>B隊(duì)列：245==>B隊(duì)列:245==>B隊(duì)列：2r-45輸出：輸出：1輸出：12輸出：123輸出：1234每一次從B隊(duì)列取出一個(gè)數(shù)時(shí)，我們就知道了在A隊(duì)列中有多少個(gè)數(shù)比B隊(duì)列的這個(gè)數(shù)大，它等于A隊(duì)列現(xiàn)在還剩的數(shù)的個(gè)數(shù)。比如，當(dāng)我們從B隊(duì)列中取出2時(shí)，我們同時(shí)知道了A隊(duì)列的3和6兩個(gè)數(shù)比2大。在合并操作中我們不斷更新A隊(duì)列中還剩幾個(gè)數(shù)，在每次從B隊(duì)列中取出一個(gè)數(shù)時(shí)把當(dāng)前A隊(duì)列剩的數(shù)目加進(jìn)最終答案里。這樣我們算出了所有“大的數(shù)在前一半，小的數(shù)在后一半”的情況，其余情況下的逆序?qū)υ谶@之前已經(jīng)被遞歸地算過了。==========================二二華麗的分割線=二==========================堆排序(HeapSort)利用了堆(Heap)這種數(shù)據(jù)結(jié)構(gòu)(什么是堆？)。堆的插入操作是平均常數(shù)的，而刪除一個(gè)根節(jié)點(diǎn)需要花費(fèi)O(logn)的時(shí)間。因此，完成堆排序需要線性時(shí)間建立堆(把所有元素依次插入一個(gè)堆)，然后用總共O(nlogn)的時(shí)間不斷取出最小的那個(gè)數(shù)。只要堆會(huì)搞，堆排序就會(huì)搞。堆在那篇日志里有詳細(xì)的說明，因此這里不重復(fù)說了。============================華麗的分割線============================快速排序(QuickSort)也應(yīng)用了遞歸的思想。我們想要把給定序列分成兩段，并對這兩段分別進(jìn)行排序。一種不錯(cuò)的想法是，選取一個(gè)數(shù)作為“關(guān)鍵字”，并把其它數(shù)分割為兩部分，把所有小于關(guān)鍵字的數(shù)都放在關(guān)鍵字的左邊，大于關(guān)鍵字的都放在右邊，然后遞歸地對左邊和右邊進(jìn)行排序。把該區(qū)間內(nèi)的所有數(shù)依次與關(guān)鍵字比較，我們就可以在線性的時(shí)間里完成分割的操作。完成分割操作有很多有技巧性的實(shí)現(xiàn)方法，比如最常用的一種是定義兩個(gè)指針，一個(gè)從前往后找找到比關(guān)鍵字大的，一個(gè)從后往前找到比關(guān)鍵字小的，然后兩個(gè)指針對應(yīng)的元素交換位置并繼續(xù)移動(dòng)指針重復(fù)剛才的過程。這只是大致的方法，具體的實(shí)現(xiàn)還有很多細(xì)節(jié)問題?？焖倥判蚴俏覀冏畛Ｓ玫拇a之一，網(wǎng)上的快速排序代碼五花八門，各種語言，各種風(fēng)格的都有。大家可以隨便找一個(gè)來看看，我說過了我們講算法但不講如何實(shí)現(xiàn)。NOIp很簡單，很多人NOIp前就背了一個(gè)快速排序代碼就上戰(zhàn)場了。當(dāng)時(shí)我把快速排序背完了，抓緊時(shí)間還順便背了一下歷史，免得晚上聽寫又不及格。不像歸并排序，快速排序的時(shí)間復(fù)雜度很難計(jì)算。我們可以看到，歸并排序的復(fù)雜度最壞情況下也是O(nlogn)的，而快速排序的最壞情況是O(n”2)的。如果每一次選的關(guān)鍵字都是當(dāng)前區(qū)間里最大(或最小)的數(shù)，那么這樣將使得每一次的規(guī)模只減小一個(gè)數(shù)，這和插入排序、選擇排序等平方級排序沒有區(qū)別。這種情況不是不可能發(fā)生。如果你每次選擇關(guān)鍵字都是選擇的該區(qū)間的第一個(gè)數(shù)，而給你的數(shù)據(jù)恰好又是已經(jīng)有序的，那你的快速排序就完蛋了。顯然，最好情況是每一次選的數(shù)正好就是中位數(shù)，這將把該區(qū)間平分為兩段，復(fù)雜度和前面討論的歸并排序一模一樣。根據(jù)這一點(diǎn)，快速排序有一些常用的優(yōu)化。比如，我們經(jīng)常從數(shù)列中隨機(jī)取一個(gè)數(shù)當(dāng)作是關(guān)鍵字(而不是每次總是取固定位置上的數(shù))，從而盡可能避免某些特殊的數(shù)據(jù)所導(dǎo)致的低效。更好的做法是隨機(jī)取三個(gè)數(shù)并選擇這三個(gè)數(shù)的中位數(shù)作為關(guān)鍵字。而對三個(gè)數(shù)的隨機(jī)取值反而將花費(fèi)更多的時(shí)間，因此我們的這三個(gè)數(shù)可以分別取數(shù)列的頭一個(gè)數(shù)、末一個(gè)數(shù)和正中間那個(gè)數(shù)。另外，當(dāng)遞歸到了一定深度發(fā)現(xiàn)當(dāng)前區(qū)間里的數(shù)只有幾個(gè)或十幾個(gè)時(shí)，繼續(xù)遞歸下去反而費(fèi)時(shí)，不如返回插入排序后的結(jié)果。這種方法同時(shí)避免了當(dāng)數(shù)字太少時(shí)遞歸操作出錯(cuò)的可能。下面我們證明，快速排序算法的平均復(fù)雜度為O(nlogn)。不同的書上有不同的解釋方法，這里我選用算法導(dǎo)論上的講法。它更有技巧性一些，更有趣一些，需要轉(zhuǎn)幾個(gè)彎才能想明白?？匆豢纯焖倥判虻拇a。正如我們提到過的那種分割方法，程序在經(jīng)過若干次與關(guān)鍵字的比較后才進(jìn)行一次交換，因此比較的次數(shù)比交換次數(shù)更多。我們通過證明一次快速排序中元素之間的比較次數(shù)平均為O(nlogn)來說明快速排序算法的平均復(fù)雜度。證明的關(guān)鍵在于，我們需要算出某兩個(gè)元素在整個(gè)算法過程中進(jìn)行過比較的概率。我們舉一個(gè)例子。假如給出了1到10這10個(gè)數(shù)，第一次選擇關(guān)鍵字7將它們分成了｛1,2,3,4,5,6｝和｛8,9,10｝兩部分，遞歸左邊時(shí)我們選擇了3作為關(guān)鍵字，使得左部分又被分割為｛1,2｝和｛4,5,6｝。我們看到，數(shù)字7與其它所有數(shù)都比較過一次，這樣才能實(shí)現(xiàn)分割操作。同樣地，1到6這6個(gè)數(shù)都需要與3進(jìn)行一次比較(除了它本身之外)。然而，3和9決不可能相互比較過，2和6也不可能進(jìn)行過比較，因?yàn)榈谝淮纬霈F(xiàn)在3和9,2和6之間的關(guān)鍵字把它們分割開了。也就是說，兩個(gè)數(shù)A(i)和A(j)比較過，當(dāng)且僅當(dāng)?shù)谝粋€(gè)滿足A(i)<=x<=A(j)的關(guān)鍵字x恰好就是A(i)或A(j)(假設(shè)A(i)比A(j)小)。我們稱排序后第i小的數(shù)為Z(i)，假設(shè)i<j，那么第一次出現(xiàn)在Z(i)和Z(j)之間的關(guān)鍵字恰好就是Z(i)或Z(j)的概率為2/(j-i+1)，這是因?yàn)楫?dāng)Z(i)和Z(j)之間還不曾有過關(guān)鍵字時(shí)，Z(i)和Z(j)處于同一個(gè)待分割的區(qū)間，不管這個(gè)區(qū)間有多大，不管遞歸到哪里了，關(guān)鍵字的選擇總是隨機(jī)的。我們得到，Z(i)和Z(j)在一次快速排序中曾經(jīng)比較過的概率為2/(j-i+1)。現(xiàn)在有四個(gè)數(shù)，2,3,5,7。排序時(shí)，相鄰的兩個(gè)數(shù)肯定都被比較過，2和5、3和7都有2/3的概率被比較過，2和7之間被比較過有2/4的可能。也就是說，如果對這四個(gè)數(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。我們可以計(jì)算出單次的快速排序平均比較了多少次：58/12=29/6。其實(shí)，它就等于6項(xiàng)概率之和，1+1+1+2/3+2/3+2/4=29/6。這其實(shí)是與期望值相關(guān)的一個(gè)公式。同樣地，如果有n個(gè)數(shù)，那么快速排序平均需要的比較次數(shù)可以寫成下面的式子。令k=j-i，我們能夠最終得到比較次數(shù)的期望值為O(nlogn)。這里用到了一個(gè)知識(shí)：1+1/2+1/3+...+1/n與logn增長速度相同，即Z(1/n)=0(logn)。它的證明放在本文的最后。在三種O(nlogn)的排序算法中，快速排序的理論復(fù)雜度最不理想，除了它以外今天說的另外兩種算法都是以最壞情況O(nlogn)的復(fù)雜度進(jìn)行排序。但實(shí)踐上看快速排序效率最高(不然為啥叫快速排序呢)，原因在于快速排序的代碼比其它同復(fù)雜度的算法更簡潔，常數(shù)時(shí)間更小?？焖倥判蛞灿幸粋€(gè)有趣的副產(chǎn)品：快速選擇給出的一些數(shù)中第k小的數(shù)。一種簡單的方法是使用上述任一種O(nlogn)的算法對這些數(shù)進(jìn)行排序并返回排序后數(shù)組的第k個(gè)元素?？焖龠x擇(QuickSelect)算法可以在平均O(n)的時(shí)間完成這一操作。它的最壞情況同快速排序一樣，也是O(n”2)。在每一次分割后，我們都可以知道比關(guān)鍵字小的數(shù)有多少個(gè)，從而確定了關(guān)鍵字在所有數(shù)中是第幾小的。我們假設(shè)關(guān)鍵字是第m小。如果k=m，那么我們就找到了答案——第k小元素即該關(guān)鍵字。否則，我們遞歸地計(jì)算左邊或者右邊：當(dāng)k<m時(shí)，我們遞歸地尋找左邊的元素中第k小的；當(dāng)k>m時(shí)，我們遞歸地尋找右邊的元素中第k-m小的數(shù)。由于我們不考慮所有的數(shù)的順序，只需要遞歸其中的一邊，因此復(fù)雜度大大降低。復(fù)雜度平均線性，我們不再具體證了。還有一種算法可以在最壞O(n)的時(shí)間里找出第k小元素。那是我見過的所有算法中最沒有實(shí)用價(jià)值的算法。那個(gè)O(n)只有理論價(jià)值。==========================二二華麗的分割線=二==========================我們前面證明過，僅僅依靠交換相鄰元素的操作，復(fù)雜度只能達(dá)到O(n”2)。于是，人們嘗試交換距離更遠(yuǎn)的元素。當(dāng)人們發(fā)現(xiàn)O(nlogn)的排序算法似乎已經(jīng)是極限的時(shí)候，又是什么制約了復(fù)雜度的下界呢？我們將要討論的是更底層的東西。我們?nèi)匀患僭O(shè)所有的數(shù)都不相等。我們總是不斷在數(shù)與數(shù)之間進(jìn)行比較。你可以試試，只用4次比較絕對不可能給4個(gè)數(shù)排出順序。每多進(jìn)行一次比較我們就又多知道了一個(gè)大小關(guān)系，從4次比較中一共可以獲知4個(gè)大小關(guān)系。4個(gè)大小關(guān)系共有2”4=16種組合方式，而4個(gè)數(shù)的順序一共有4!=24種。也就是說，4次比較可能出現(xiàn)的結(jié)果數(shù)目不足以區(qū)分24種可能的順序。更一般地，給你n個(gè)數(shù)叫你排序，可能的答案共有n!個(gè)，k次比較只能區(qū)分2”k種可能，于是只有2”k>=n!時(shí)才有可能排出順序。等號兩邊取對數(shù)，于是，給n個(gè)數(shù)排序至少需要log2(n!)次。注意，我們并沒有說明一定能通過log2(n!)次比較排出順序。雖然2”5=32超過了4!，但這不足以說明5次比較一定足夠。如何用5次比較確定4個(gè)數(shù)的大小關(guān)系還需要進(jìn)一步研究。第一次例外發(fā)生在n=12的時(shí)候，雖然2”29>12!，但現(xiàn)已證明給12個(gè)數(shù)排序最少需要30次比較。我們可以證明log(n!)的增長速度與nlogn相同，即log(n!)=0(nlogn)。這是排序所需要的最少的比較次數(shù)，它給出了排序復(fù)雜度的一個(gè)下界。log(n!)=O(nlogn)的證明也附在本文最后。這篇日志的第三題中證明log2(N)是最優(yōu)時(shí)用到了幾乎相同的方法。那種“用天平稱出重量不同的那個(gè)球至少要稱幾次”一類題目也可以用這種方法來解決。事實(shí)上，這里有一整套的理論，它叫做信息論。信息論是由香農(nóng)(Shannon)提出的。他用對數(shù)來表示信息量，用熵來表示可能的情況的隨機(jī)性，通過運(yùn)算可以知道你目前得到的信息能夠怎樣影響最終結(jié)果的確定。如果我們的信息量是以2為底的，那信息論就變成信息學(xué)了。從根本上說，計(jì)算機(jī)的一切信息就是以2為底的信息量(bits二binarydigits)，因此我們常說香農(nóng)是數(shù)字通信之父。信息論和熱力學(xué)關(guān)系密切，比如熵的概念是直接從熱力學(xué)的熵定義引申過來的。和這個(gè)有關(guān)的東西已經(jīng)嚴(yán)重偏題了，這里不說了，有興趣可以去看《信息論與編碼理論》。我對這個(gè)也很有興趣，半懂不懂的，很想了解更多的東西，有興趣的同志不妨加入討論。物理學(xué)真的很神奇，利用物理學(xué)可以解決很多純數(shù)學(xué)問題，我有時(shí)間的話可以舉一些例子。我他媽的為啥要選文科呢。后面將介紹的三種排序是線性時(shí)間復(fù)雜度，因?yàn)椋鼈兣判驎r(shí)根本不是通過互相比較來確定大小關(guān)系的。附1：Z(1/n)=0(logn)的證明首先我們證明，Z(1/n)=O(logn)。在式子1+1/2+1/3+1/4+1/5+...中，我們把1/3變成1/2，使得兩個(gè)1/2加起來湊成一個(gè)1