從零開(kāi)始學(xué)算法：十種排序算法介紹（上）
From:Martix67【牛啊！】
今天我正式開(kāi)始按照
我的目錄寫我的OI心得了。我要把
我所有學(xué)到的OI知識(shí)傳給以后千千萬(wàn)萬(wàn)的OIer。以前寫過(guò)的一些東西不重復(fù)寫了，但我最后將會(huì)重新整理，使之成為一個(gè)完整的教程。
按照
我的目錄，講任何東西之前我都會(huì)先介紹時(shí)間復(fù)雜度的相關(guān)知識(shí)，以后動(dòng)不動(dòng)就會(huì)扯到這個(gè)東西。這個(gè)已經(jīng)寫過(guò)了，你可以在
這里看到那篇又臭又長(zhǎng)的文章。在講
排序算法的過(guò)程中，我們將始終圍繞時(shí)間復(fù)雜度的內(nèi)容進(jìn)行說(shuō)明。
我把這篇文章稱之為“從零開(kāi)始學(xué)算法”，因?yàn)榕判蛩惴ㄊ亲罨A(chǔ)的算法，介紹
算法時(shí)從各種排序算法入手是最好不過(guò)的了。
給出n個(gè)數(shù)，怎樣將它們從小到大排序？下面一口氣講三種常用的算法，它們是最簡(jiǎn)單的、
最顯然的、最容易想到的。選擇排序(Selection
Sort)是說(shuō)，每次從數(shù)列中找出一個(gè)最小的數(shù)放到最前面來(lái)，再?gòu)氖Ｏ碌膎-1個(gè)數(shù)中選擇一個(gè)最小的，不斷做下去。插入排序(Insertion
Sort)是，每次從數(shù)列中取一個(gè)還沒(méi)有取出過(guò)的數(shù)，并按照大小關(guān)系插入到已經(jīng)取出的數(shù)中使得已經(jīng)取出的數(shù)仍然有序。冒泡排序(Bubble
Sort)分為若干趟進(jìn)行，每一趟排序從前往后比較每?jī)蓚€(gè)相鄰的元素的大小（因此一趟排序要比較n-1對(duì)位置相鄰的數(shù)）并在每次發(fā)現(xiàn)前面的那個(gè)數(shù)比緊接它
后的數(shù)大時(shí)交換位置；進(jìn)行足夠多趟直到某一趟跑完后發(fā)現(xiàn)這一趟沒(méi)有進(jìn)行任何交換操作（最壞情況下要跑n-1趟，這種情況在最小的數(shù)位于給定數(shù)列的最后面時(shí)
發(fā)生）。事實(shí)上，在第一趟冒泡結(jié)束后，最后面那個(gè)數(shù)肯定是最大的了，于是第二次只需要對(duì)前面n-1個(gè)數(shù)排序，這又將把這n-1個(gè)數(shù)中最小的數(shù)放到整個(gè)數(shù)列
的倒數(shù)第二個(gè)位置。這樣下去，冒泡排序第i趟結(jié)束后后面i個(gè)數(shù)都已經(jīng)到位了，第i+1趟實(shí)際上只考慮前n-i個(gè)數(shù)（需要的比較次數(shù)比前面所說(shuō)的n-1要
小）。這相當(dāng)于用數(shù)學(xué)歸納法證明了冒泡排序的正確性：實(shí)質(zhì)與選擇排序相同。上面的三個(gè)算法描述可能有點(diǎn)模糊了，沒(méi)明白的話網(wǎng)上找資料，代碼和動(dòng)畫(huà)演示遍地
都是。
這
三種算法非常容易理解，因?yàn)槲覀兩町?dāng)中經(jīng)常在用。比如，班上的MM搞選美活動(dòng)，有人叫我給所有MM排個(gè)名。我們通常會(huì)用選擇排序，即先找出自己認(rèn)為最漂
亮的，然后找第二漂亮的，然后找第三漂亮的，不斷找剩下的人中最滿意的。打撲克牌時(shí)我們希望抓完牌后手上的牌是有序的，三個(gè)8挨在一起，后面緊接著兩個(gè)
9。這時(shí)，我們會(huì)使用插入排序，每次拿到一張牌后把它插入到手上的牌中適當(dāng)?shù)奈恢谩Ｊ裁磿r(shí)候我們會(huì)用冒泡排序呢？比如，體育課上從矮到高排隊(duì)時(shí)，站隊(duì)完畢
后總會(huì)有人出來(lái)，比較挨著的兩個(gè)人的身高，指揮到：你們倆調(diào)換一下，你們倆換一下。
這是很有啟發(fā)性的。這告訴我們，什么時(shí)候用什么排序最
好。當(dāng)人們渴望先知道排在前面的是誰(shuí)時(shí)，我們用選擇排序；
當(dāng)我們不斷拿
到新的數(shù)并想保持已有的數(shù)始終有序時(shí)，我們用插入排序；當(dāng)給出的數(shù)列已經(jīng)比較有序，只需要小幅度的調(diào)整一下時(shí)，我們用冒泡排序。
我
們來(lái)算一下最壞情況下三種算法各需要多少次比較和賦值操作。
選擇排序在第i次選擇時(shí)賦值和比較都需要n-i次（在n-i+1個(gè)數(shù)中選一個(gè)
出來(lái)作為當(dāng)前最小值，其余n-i個(gè)數(shù)與當(dāng)前最小值比較并不斷更新當(dāng)前最小值），然后需要一次賦值操作。總共需要n(n-1)/2次比較與n(n-1)
/2+n次賦值。
插入排序在第i次尋找插入位置時(shí)需要最多i-1次比較（從后往前找到第一個(gè)比待插入的數(shù)小的數(shù)，最壞情況發(fā)生在這個(gè)數(shù)是
所有已經(jīng)取出的數(shù)中最小的一個(gè)的時(shí)候），在已有數(shù)列中給新的數(shù)騰出位置需要i-1次賦值操作來(lái)實(shí)現(xiàn)，還需要兩次賦值借助臨時(shí)變量把新取出的數(shù)搬進(jìn)搬出。也
就是說(shuō)，最壞情況下比較需要n(n-1)/2次，賦值需要n(n-1)/2+2n次。我這么寫有點(diǎn)誤導(dǎo)人，大家不要以為程序的實(shí)現(xiàn)用了兩個(gè)數(shù)組哦，其實(shí)一
個(gè)數(shù)組就夠了，看看上面的演示就知道了。我只說(shuō)算法，一般不寫如何實(shí)現(xiàn)。學(xué)算法的都是強(qiáng)人，知道算法了都能寫出一個(gè)漂亮的代碼來(lái)。
冒泡排
序第i趟排序需要比較n-i次，n-1趟排序總共n(n-1)/2次。給出的序列逆序排列是最壞的情況，這時(shí)每一次比較都要進(jìn)行交換操作。一次交換操作需
要3次賦值實(shí)現(xiàn)，因此冒泡排序最壞情況下需要賦值3n(n-1)/2次。
按照漸進(jìn)復(fù)雜度理論，忽略所有的常數(shù)，三種排序的最壞情況下復(fù)雜
度都是一樣的：O(n^2)。但實(shí)際應(yīng)用中三種排序的效率并不相同。實(shí)踐證明（政治考試時(shí)每道大題都要用這四個(gè)字），插入排序是最快的（雖然最壞情況下與
選擇排序相當(dāng)甚至更糟），因?yàn)槊恳淮尾迦霑r(shí)尋找插入的位置多數(shù)情況只需要與已有數(shù)的一部分進(jìn)行比較（你可能知道這還能二分）。你或許會(huì)說(shuō)冒泡排序也可以在
半路上完成，還沒(méi)有跑到第n-1趟就已經(jīng)有序。但冒泡排序的交換操作更費(fèi)時(shí)，而插入排序中找到了插入的位置后移動(dòng)操作只需要用賦值就能完成（你可能知道這
還能用move）。本文后面將介紹的一種算法就利用插入排序的這些優(yōu)勢(shì)。
我們證明了，三種排序方法在最壞情況下時(shí)間復(fù)雜度都是
O(n^2)。但大家想過(guò)嗎，這只是最壞情況下的。在很多時(shí)候，復(fù)雜度沒(méi)有這么大，因?yàn)椴迦牒兔芭菰跀?shù)列已經(jīng)比較有序的情況下需要的操作遠(yuǎn)遠(yuǎn)低于n^2次
（最好情況下甚至是線性的）。拋開(kāi)選擇排序不說(shuō)（因?yàn)樗膹?fù)雜度是“死”的，對(duì)于選擇排序沒(méi)有什么“好”的情況），我們下面探討插入排序和冒泡排序在特定
數(shù)據(jù)和平均情況下的復(fù)雜度。
你會(huì)發(fā)現(xiàn)，如果把插入排序中的移動(dòng)賦值操作看作是把當(dāng)前取出的元素與前面取出的且比它大的數(shù)逐一交換，那插入
排序和冒泡排序?qū)?shù)據(jù)的變動(dòng)其實(shí)都是相鄰元素的交換操作。下面我們說(shuō)明，若只能對(duì)數(shù)列中相鄰的數(shù)進(jìn)行交換操作，如何計(jì)算使得n個(gè)數(shù)變得有序最少需要的交換
次數(shù)。
我們定義逆序?qū)Φ母拍睢＜僭O(shè)我們要把數(shù)列從小到大排序，一個(gè)逆序?qū)κ侵傅脑谠瓟?shù)列中，左邊的某個(gè)數(shù)比右邊的大。也就是說(shuō)，如果找到
了某個(gè)i和j使得i<j且Ai>Aj，我們就說(shuō)我們找到了一個(gè)逆序?qū)Α１热缯f(shuō)，數(shù)列3,1,4,2中有三個(gè)逆序?qū)Γ粋€(gè)已經(jīng)有序的數(shù)列逆序
對(duì)個(gè)數(shù)為0。我們發(fā)現(xiàn)，交換兩個(gè)相鄰的數(shù)最多消除一個(gè)逆序?qū)Γ颐芭菖判颍ɑ虿迦肱判颍┲械囊淮谓粨Q恰好能消除一個(gè)逆序?qū)ΑＤ敲达@然，原數(shù)列中有多少個(gè)逆
序?qū)γ芭菖判颍ɑ虿迦肱判颍┚托枰嗌俅谓粨Q操作，這個(gè)操作次數(shù)不可能再少。
若給出的n個(gè)數(shù)中有m個(gè)逆序?qū)Γ迦肱判虻臅r(shí)間復(fù)雜度可以說(shuō)
是O(m+n)的，而冒泡排序不能這么說(shuō)，因?yàn)槊芭菖判蛴泻芏?#8220;無(wú)用”的比較（比較后沒(méi)有交換），這些無(wú)用的比較超過(guò)了O(m+n)個(gè)。從這個(gè)意義上說(shuō)，
插入排序仍然更為優(yōu)秀，因?yàn)槊芭菖判虻膹?fù)雜度要受到它跑的趟數(shù)的制約。一個(gè)典型的例子是這樣的數(shù)列：8, 2, 3, 4, 5, 6, 7,
1。在這樣的輸入數(shù)據(jù)下插入排序的優(yōu)勢(shì)非常明顯，冒泡排序只能哭著喊上天不公。
然而，我們并不想計(jì)算排序算法對(duì)于某個(gè)特定數(shù)據(jù)的效率。我
們真正關(guān)心的是，對(duì)于所有可能出現(xiàn)的數(shù)據(jù)，算法的平均復(fù)雜度是多少。不用激動(dòng)了，平均復(fù)雜度并不會(huì)低于平方。下面證明，兩種算法的平均復(fù)雜度仍然是
O(n^2)的。
我們僅僅證明算法需要的交換次數(shù)平均為O(n^2)就足夠了。前面已經(jīng)說(shuō)過(guò)，它們需要的交換次數(shù)與逆序?qū)Φ膫€(gè)數(shù)相同。我
們將證明，n個(gè)數(shù)的數(shù)列中逆序?qū)€(gè)數(shù)平均O(n^2)個(gè)。
計(jì)算的方法是十分巧妙的。如果把給出的數(shù)列反過(guò)來(lái)（從后往前倒過(guò)來(lái)寫），你會(huì)發(fā)
現(xiàn)原來(lái)的逆序?qū)ΜF(xiàn)在變成順序的了，而原來(lái)所有的非逆序?qū)ΜF(xiàn)在都成逆序了。正反兩個(gè)數(shù)列的逆序?qū)€(gè)數(shù)加起來(lái)正好就是數(shù)列所有數(shù)對(duì)的個(gè)數(shù)，它等于n(n-
1)/2。于是，平均每個(gè)數(shù)列有n(n-1)/4個(gè)逆序?qū)Α：雎猿?shù)，逆序?qū)ζ骄鶄€(gè)數(shù)O(n^2)。
上面的討論啟示我們，要想搞出一個(gè)復(fù)
雜度低于平方級(jí)別的排序算法，我們需要想辦法能把離得老遠(yuǎn)的兩個(gè)數(shù)進(jìn)行操作。
人們想啊想啊想啊，怎么都想不出怎樣才能搞出復(fù)雜度
低于平方的算法。后來(lái)，英雄出現(xiàn)了，Donald Shell發(fā)明了一種新的算法，我們將證明它的復(fù)雜度最壞情況下也沒(méi)有O(n^2)
（似乎有人不喜歡研究正確性和復(fù)雜度的證明，我會(huì)用實(shí)例告訴大家，這些證明是非常有意思的）。他把這種算法叫做Shell增量排序算法（大家常說(shuō)的希爾排
序）。
Shell排序算法依賴一種稱之為“排序增量”的數(shù)列，不同的增量將導(dǎo)致不同的效率。假如我們對(duì)20個(gè)數(shù)進(jìn)行排序，使用的增量為
1,3,7。那么，我們首先對(duì)這20個(gè)數(shù)進(jìn)行“7-排序”(7-sortedness)。所謂7-排序，就是按照位置除以7的余數(shù)分組進(jìn)行排序。具體地
說(shuō)，我們將把在1、8、15三個(gè)位置上的數(shù)進(jìn)行排序，將第2、9、16個(gè)數(shù)進(jìn)行排序，依此類推。這樣，對(duì)于任意一個(gè)數(shù)字k，單看A(k),
A(k+7), A(k+14),
…這些數(shù)是有序的。7-排序后，我們接著又進(jìn)行一趟3-排序（別忘了我們使用的排序增量為1,3,7）。最后進(jìn)行1-排序（即普通的排序）后整個(gè)
Shell算法完成。看看我們的例子：
3 7 9 0 5 1 6
8 4 2 0 6 1 5 7 3 4 9 8 2 <-- 原數(shù)列
3 3 2 0 5 1 5 7 4 4 0 6 1 6 8
7 9 9 8 2 <-- 7-排序后
0 0 1 1 2 2 3 3 4 4 5 6 5 6 8 7 7 9 8
9 <-- 3-排序后
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 <--
1-排序后（完成）
在每一趟、每一組的排序中我們總是使用插入排序。仔細(xì)觀察上面的例子你會(huì)發(fā)現(xiàn)是什么導(dǎo)致了
Shell排序的高效。對(duì)，每一趟排序?qū)⑹沟脭?shù)列部分有序，從而使得以后的插入排序很快找到插入位置。我們下面將緊緊圍繞這一點(diǎn)來(lái)證明Shell排序算法
的時(shí)間復(fù)雜度上界。
只要排序增量的第一個(gè)數(shù)是1，Shell排序算法就是正確的。但是不同的增量將導(dǎo)致不同的時(shí)間復(fù)雜度。我們上面例子中
的增量(1, 3, 7, 15, 31, …,
2^k-1)是使用最廣泛的增量序列之一，可以證明使用這個(gè)增量的時(shí)間復(fù)雜度為O(n√n)。這個(gè)證明很簡(jiǎn)單，大家可以參看一些其它的資料，我們今天不證
明它。今天我們證明，使用增量1, 2, 3, 4, 6, 8, 9, 12, 16, …, 2^p*3^q，時(shí)間復(fù)雜度為O(n*(log
n)^2)。
很顯然，任何一個(gè)大于1的正整數(shù)都可以表示為2x+3y，其中x和y是非負(fù)整數(shù)。于是，如果一個(gè)數(shù)列已經(jīng)是2-排序的且是
3-排序的，那么對(duì)于此時(shí)數(shù)列中的每一個(gè)數(shù)A(i)，它的左邊比它大的只有可能是A(i-1)。A2絕對(duì)不可能比A12大，因?yàn)?0可以表示為兩個(gè)2和兩
個(gè)3的和，則A2<A4<A6<A9<A12。那么，在這個(gè)增量中的1-排序時(shí)每個(gè)數(shù)找插入位置只需要比較一次。一共有n個(gè)數(shù)，
所以1-排序是O(n)的。事實(shí)上，這個(gè)增量中的2-排序也是O(n)，因?yàn)樵?-排序之前，這個(gè)數(shù)列已經(jīng)是4-排序且6-排序過(guò)的，只看數(shù)列的奇數(shù)項(xiàng)或
者偶數(shù)項(xiàng)（即單看每一組）的話就又成了剛才的樣子。這個(gè)增量序列巧妙就巧妙在，如果我們要進(jìn)行h-排序，那么它一定是2h-排序過(guò)且3h-排序過(guò)，于是處
理每個(gè)數(shù)A(i)的插入時(shí)就只需要和A(i-h)進(jìn)行比較。這個(gè)結(jié)論對(duì)于最開(kāi)始幾次（h值較大時(shí)）的h-排序同樣成立，當(dāng)2h、3h大于n時(shí)，按照定義，
我們也可以認(rèn)為數(shù)列是2h-排序和3h-排序的，這并不影響上述結(jié)論的正確性（你也可以認(rèn)為h太大以致于排序時(shí)每一組里的數(shù)字不超過(guò)3個(gè)，屬于常數(shù)級(jí)）。
現(xiàn)在，這個(gè)增量中的每一趟排序都是O(n)的，我們只需要數(shù)一下一共跑了多少趟。也就是說(shuō)，我們現(xiàn)在只需要知道小于n的數(shù)中有多少個(gè)數(shù)具有2^p*3^q
的形式。要想2^p*3^q不超過(guò)n，p的取值最多O(log n)個(gè)，q的取值最多也是O(log
n)個(gè)，兩兩組合的話共有O(logn*logn)種情況。于是，這樣的增量排序需要跑O((log
n)^2)趟，每一趟的復(fù)雜度O(n)，總的復(fù)雜度為O(n*(log n)^2)。早就說(shuō)過(guò)了，證明時(shí)間復(fù)雜度其實(shí)很有意思。
我們自然
會(huì)想，有沒(méi)有能使復(fù)雜度降到O(nlogn)甚至更低的增量序列。很遺憾，現(xiàn)在沒(méi)有任何跡象表明存在O(nlogn)的增量排序。但事實(shí)上，很多時(shí)候
Shell排序的實(shí)際效率超過(guò)了O(nlogn)的排序算法。
后面我們將介紹三種O(nlogn)的排序算法和三種線性時(shí)間的排
序算法。最后我們將以外部排序和排序網(wǎng)絡(luò)結(jié)束這一章節(jié)。
很多人問(wèn)到我關(guān)于轉(zhuǎn)貼的問(wèn)題。我歡迎除商業(yè)目的外任何形式的轉(zhuǎn)貼（論壇、
Blog、Wiki、個(gè)人網(wǎng)站、PodCast，甚至做成ppt、pdf），但一定要注明出處，最好保留原始鏈接。我的網(wǎng)站需要點(diǎn)反向鏈接才能在網(wǎng)絡(luò)中生
存下去，大家也都可以關(guān)注并且推廣這個(gè)Blog。我一直支持cc版權(quán)協(xié)議，因此發(fā)現(xiàn)了文章中的問(wèn)題或者想要補(bǔ)充什么東西盡管提出來(lái)，好讓更多的人學(xué)習(xí)到好
東西。我昨天看Blog上原來(lái)寫的一些東西，居然連著發(fā)現(xiàn)了幾個(gè)錯(cuò)誤式子和錯(cuò)別字，好奇大家居然沒(méi)有提出來(lái)。發(fā)現(xiàn)了問(wèn)題真的要告訴我，即使格式有點(diǎn)問(wèn)題也
要說(shuō)一下，決不能讓它那么錯(cuò)著。另外有什么建議或想法也請(qǐng)說(shuō)一下，我希望聽(tīng)到不同的聲音不同的見(jiàn)解，好讓我決定這類文章以后的發(fā)展方向。
Matrix67
原創(chuàng)
轉(zhuǎn)貼請(qǐng)注明出處
從零開(kāi)始學(xué)算法：十種排序算法介紹（中）
本文被華麗的分割線分為了四段。對(duì)
于O(nlogn)的排序算法，我們?cè)敿?xì)介紹歸并排序并證明歸并排序的時(shí)間復(fù)雜度，然后簡(jiǎn)單介紹堆排序，之后給出快速排序的基本思想和復(fù)雜度證明。最后我
們將證明，O(nlogn)在理論上已經(jīng)達(dá)到了最優(yōu)。學(xué)過(guò)OI的人一般都學(xué)過(guò)這些很基礎(chǔ)的東西，大多數(shù)OIer們不必看了。為了保持系列文章的完整性，我
還是花時(shí)間寫了一下。
首先考慮一個(gè)簡(jiǎn)單的問(wèn)題：如何在線性的時(shí)間內(nèi)將兩個(gè)有序隊(duì)列合并為一個(gè)有序隊(duì)列（并輸出）？
A
隊(duì)列：1 3 5 7 9
B隊(duì)列：1 2 7 8 9
看上面的例子，AB兩個(gè)序列都是已經(jīng)有序的了。在給出數(shù)據(jù)已經(jīng)有序的情況下，我
們會(huì)發(fā)現(xiàn)很多神奇的事，比如，我們將要輸出的第一個(gè)數(shù)一定來(lái)自于這兩個(gè)序列各自最前面的那個(gè)數(shù)。兩個(gè)數(shù)都是1，那么我們隨便取出一個(gè)（比如A隊(duì)列的那個(gè)
1）并輸出：
A隊(duì)列：1 3 5 7 9
B隊(duì)列：1
2 7 8 9
輸出：1
注意，我們?nèi)〕隽艘粋€(gè)數(shù)，在原數(shù)列中刪除這個(gè)數(shù)。刪除操作是通過(guò)移動(dòng)隊(duì)首指針實(shí)
現(xiàn)的，否則復(fù)雜度就高了。
現(xiàn)在，A隊(duì)列打頭的數(shù)變成3了，B隊(duì)列的隊(duì)首仍然是1。此時(shí)，我們?cè)俦容^3和1哪個(gè)大并輸出小的那個(gè)數(shù)：
A隊(duì)列：1 3
5 7 9
B隊(duì)列：1 2 7 8 9
輸出：1 1
接
下來(lái)的幾步如下：
A隊(duì)列：1 3 5 7
9 A隊(duì)列：1 3 5 7 9 A隊(duì)列：1 3 5 7
9 A隊(duì)列：1 3 5 7 9
B隊(duì)列：1 2 7 8 9 ==> B隊(duì)列：1
2 7 8 9 ==> B隊(duì)列：1 2 7 8 9 ==> B隊(duì)列：1 2 7
8 9 ……
輸出：1 1 2 輸出：1 1 2 3 輸出：1 1 2 3
5 輸出：1 1 2 3 5 7
我希望你明白了這是怎么做的。這個(gè)做法顯然是正確的，復(fù)雜
度顯然是線性。
歸并排序(Merge
Sort)將會(huì)用到上面所說(shuō)的合并操作。給出一個(gè)數(shù)列，歸并排序利用合并操作在O(nlogn)的時(shí)間內(nèi)將數(shù)列從小到大排序。歸并排序用的是分治
(Divide and
Conquer)的思想。首先我們把給出的數(shù)列平分為左右兩段，然后對(duì)兩段數(shù)列分別進(jìn)行排序，最后用剛才的合并算法把這兩段（已經(jīng)排過(guò)序的）數(shù)列合并為一
個(gè)數(shù)列。有人會(huì)問(wèn)“對(duì)左右兩段數(shù)列分別排序時(shí)用的什么排序”么？答案是：用歸并排序。也就是說(shuō)，我們遞歸地把每一段數(shù)列又分成兩段進(jìn)行上述操作。你不需要
關(guān)心實(shí)際上是怎么操作的，我們的程序代碼將遞歸調(diào)用該過(guò)程直到數(shù)列不能再分（只有一個(gè)數(shù)）為止。
初看這個(gè)算法時(shí)有人會(huì)誤以為時(shí)間復(fù)雜度相
當(dāng)高。我們下面給出的一個(gè)圖將用非遞歸的眼光來(lái)看歸并排序的實(shí)際操作過(guò)程，供大家參考。我們可以借助這個(gè)圖證明，歸并排序算法的時(shí)間復(fù)雜度為
O(nlogn)。
[3] [1] [4] [1] [5] [9]
[2] [7]
\ / \ / \ / \ /
[1 3] [1 4] [5 9] [2
7]
\ / \ /
[1 1 3 4] [2 5 7 9]
\ /
[1 1 2 3 4 5 7 9]
上圖中的每一個(gè)“ \ /
”表示的是上文所述的線性時(shí)間合并操作。上圖用了4行來(lái)圖解歸并排序。如果有n個(gè)數(shù)，表示成上圖顯然需要O(logn)行。每一行的合并操作復(fù)雜度總和都
是O(n)，那么logn行的總復(fù)雜度為O(nlogn)。這相當(dāng)于用遞歸樹(shù)的方法對(duì)歸并排序的復(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)。不斷展開(kāi)這個(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ì)算幾何部分舉
一大堆類似的例子。
如果你第一次見(jiàn)到這么詭異的算法，你可能會(huì)對(duì) 這個(gè) 感興趣。
分治是遞歸的一種應(yīng)用。這是我們第一次接觸遞歸運(yùn)算。下面說(shuō)的快速排序也是用的遞歸的思想。遞歸程序的復(fù)雜度分析通常和上面一樣，主定理(Master
Theory)可以簡(jiǎn)化這個(gè)分析過(guò)程。主定理和本文內(nèi)容離得太遠(yuǎn)，我們以后也不會(huì)用它，因此我們不介紹它，大家可以自己去查。有個(gè)名詞在這里的話找學(xué)習(xí)資
料將變得非常容易，我最怕的就是一個(gè)東西不知道叫什么名字，半天找不到資料。
歸并排序有一個(gè)有趣的副產(chǎn)品。利用歸并排序能夠在
O(nlogn)的時(shí)間里計(jì)算出給定序列里逆序?qū)Φ膫€(gè)數(shù)。你可以用任何一種平衡二叉樹(shù)來(lái)完成這個(gè)操作，但用歸并排序統(tǒng)計(jì)逆序?qū)Ω奖恪Ｎ覀冇懻撃嫘驅(qū)σ话?
是說(shuō)的一個(gè)排列中的逆序?qū)Γ虼诉@里我們假設(shè)所有數(shù)不相同。假如我們想要數(shù)1, 6, 3, 2, 5,
4中有多少個(gè)逆序?qū)Γ覀兪紫劝堰@個(gè)數(shù)列分為左右兩段。那么一個(gè)逆序?qū)χ豢赡苡腥N情況：兩個(gè)數(shù)都在左邊，兩個(gè)數(shù)都在右邊，一個(gè)在左一個(gè)在右。在左右兩段
分別處理完后，線性合并的過(guò)程中我們可以順便算出所有第三種情況的逆序?qū)τ卸嗌賯€(gè)。換句話說(shuō)，我們能在線性的時(shí)間里統(tǒng)計(jì)出A隊(duì)列的某個(gè)數(shù)比B隊(duì)列的某個(gè)數(shù)
大有多少種情況。
A隊(duì)列：1 3 6 A隊(duì)列：1
3 6 A隊(duì)列：1 3 6 A隊(duì)列：1 3 6 A隊(duì)列：1 3
6
B隊(duì)列：2 4 5 ==> B隊(duì)列：2 4 5 ==> B隊(duì)列：2 4 5
==> B隊(duì)列：2 4 5 ==> B隊(duì)列：2 4 5 ……
輸
出： 輸出：1 輸出：1 2 輸出：1 2
3 輸出：1 2 3 4
每一次從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)被遞歸地算過(guò)了。
============================華麗的分割
線============================
堆排序(Heap Sort)利用了堆(Heap)這種數(shù)據(jù)結(jié)構(gòu)（ 什么是堆？ ）。
堆的插入操作是平均常數(shù)的，而刪除一個(gè)根節(jié)點(diǎn)需要花費(fèi)O(log
n)的時(shí)間。因此，完成堆排序需要線性時(shí)間建立堆（把所有元素依次插入一個(gè)堆），然后用總共O(nlogn)的時(shí)間不斷取出最小的那個(gè)數(shù)。只要堆會(huì)搞，堆
排序就會(huì)搞。堆在那篇日志里有詳細(xì)的說(shuō)明，因此這里不重復(fù)說(shuō)了。
============================華麗的分割
線============================
快速排序(Quick
Sort)也應(yīng)用了遞歸的思想。我們想要把給定序列分成兩段，并對(duì)這兩段分別進(jìn)行排序。一種不錯(cuò)的想法是，選取一個(gè)數(shù)作為“關(guān)鍵字”，并把其它數(shù)分割為兩
部分，把所有小于關(guān)鍵字的數(shù)都放在關(guān)鍵字的左邊，大于關(guān)鍵字的都放在右邊，然后遞歸地對(duì)左邊和右邊進(jìn)行排序。把該區(qū)間內(nèi)的所有數(shù)依次與關(guān)鍵字比較，我們就
可以在線性的時(shí)間里完成分割的操作。完成分割操作有很多有技巧性的實(shí)現(xiàn)方法，比如最常用的一種是定義兩個(gè)指針，一個(gè)從前往后找找到比關(guān)鍵字大的，一個(gè)從后
往前找到比關(guān)鍵字小的，然后兩個(gè)指針對(duì)應(yīng)的元素交換位置并繼續(xù)移動(dòng)指針重復(fù)剛才的過(guò)程。這只是大致的方法，具體的實(shí)現(xiàn)還有很多細(xì)節(jié)問(wèn)題。快速排序是我們最
常用的代碼之一，網(wǎng)上的快速排序代碼五花八門，各種語(yǔ)言，各種風(fēng)格的都有。大家可以隨便找一個(gè)來(lái)看看，我說(shuō)過(guò)了我們講算法但不講如何實(shí)現(xiàn)。NOIp很簡(jiǎn)
單，很多人NOIp前就背了一個(gè)快速排序代碼就上戰(zhàn)場(chǎng)了。當(dāng)時(shí)我把快速排序背完了，抓緊時(shí)間還順便背了一下歷史，免得晚上聽(tīng)寫又不及格。
不
像歸并排序，快速排序的時(shí)間復(fù)雜度很難計(jì)算。我們可以看到，歸并排序的復(fù)雜度最壞情況下也是O(nlogn)的，而快速排序的最壞情況是O(n^2)的。
如果每一次選的關(guān)鍵字都是當(dāng)前區(qū)間里最大（或最小）的數(shù)，那么這樣將使得每一次的規(guī)模只減小一個(gè)數(shù)，這和插入排序、選擇排序等平方級(jí)排序沒(méi)有區(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)鍵字。而對(duì)三個(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)。不同的書(shū)上有不同的解釋方法，這里我選用算法導(dǎo)論上的講法。它更有技巧性一些，更有趣一些，需
要轉(zhuǎn)幾個(gè)彎才能想明白。
看一看快速排序的代碼。正如我們提到過(guò)的那種分割方法，程序在經(jīng)過(guò)若干次與關(guān)鍵字的比較后才進(jìn)行一次交換，因此比
較的次數(shù)比交換次數(shù)更多。我們通過(guò)證明一次快速排序中元素之間的比較次數(shù)平均為O(nlogn)來(lái)說(shuō)明快速排序算法的平均復(fù)雜度。證明的關(guān)鍵在于，我們需
要算出某兩個(gè)元素在整個(gè)算法過(guò)程中進(jìn)行過(guò)比較的概率。
我們舉一個(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ù)都比較過(guò)一次，這樣才能實(shí)現(xiàn)分割操作。同樣地，1到6這6個(gè)數(shù)都需要與3進(jìn)行一次比較（除了它本身之外）。然而，3和9決不可能相互比
較過(guò)，2和6也不可能進(jìn)行過(guò)比較，因?yàn)榈谝淮纬霈F(xiàn)在3和9，2和6之間的關(guān)鍵字把它們分割開(kāi)了。也就是說(shuō)，兩個(gè)數(shù)A(i)和A(j)比較過(guò)，當(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ò)關(guān)鍵字時(shí)，Z(i)和Z(j)處于同一個(gè)待分割的區(qū)間，不管這個(gè)區(qū)間
有多大，不管遞歸到哪里了，關(guān)鍵字的選擇總是隨機(jī)的。我們得到，Z(i)和Z(j)在一次快速排序中曾經(jīng)比較過(guò)的概率為2/(j-i+1)。
現(xiàn)
在有四個(gè)數(shù)，2,3,5,7。排序時(shí)，相鄰的兩個(gè)數(shù)肯定都被比較過(guò)，2和5、3和7都有2/3的概率被比較過(guò)，2和7之間被比較過(guò)有2/4的可能。也就是
說(shuō)，如果對(duì)這四個(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與log n增長(zhǎng)速度相同，即Σ(1/n)=Θ(log n)。它的證明放在本文的最后。
在
三種O(nlogn)的排序算法中，快速排序的理論復(fù)雜度最不理想，除了它以外今天說(shuō)的另外兩種算法都是以最壞情況O(nlogn)的復(fù)雜度進(jìn)行排序。但
實(shí)踐上看快速排序效率最高（不然為啥叫快速排序呢），原因在于快速排序的代碼比其它同復(fù)雜度的算法更簡(jiǎn)潔，常數(shù)時(shí)間更小。
快速排
序也有一個(gè)有趣的副產(chǎn)品：快速選擇給出的一些數(shù)中第k小的數(shù)。一種簡(jiǎn)單的方法是使用上述任一種O(nlogn)的算法對(duì)這些數(shù)進(jìn)行排序并返回排序后數(shù)組的
第k個(gè)元素。快速選擇(Quick
Select)算法可以在平均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小元素。那是我見(jiàn)過(guò)的所有算法中最沒(méi)有實(shí)用價(jià)值的算法。那個(gè)O(n)只有理論價(jià)值。
============================
華麗的分割線============================
我們前面證明過(guò)，僅僅依靠交換相鄰元素的操作，復(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次比較絕對(duì)不可能給
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種。也就是說(shuō)，4次比較可能出現(xiàn)的結(jié)果數(shù)目不足以區(qū)分24種可能的順序。更一般地，給你n個(gè)數(shù)叫你排序，可能的答案共有n!
個(gè)，k次比較只能區(qū)分2^k種可能，于是只有2^k>=n!時(shí)才有可能排出順序。等號(hào)兩邊取對(duì)數(shù)，于是，給n個(gè)數(shù)排序至少需要log2(n!)次。
注意，我們并沒(méi)有說(shuō)明一定能通過(guò)log2(n!)次比較排出順序。雖然2^5=32超過(guò)了4!，但這不足以說(shuō)明5次比較一定足夠。如何用5次比較確定4個(gè)
數(shù)的大小關(guān)系還需要進(jìn)一步研究。第一次例外發(fā)生在n=12的時(shí)候，雖然2^29>12!，但現(xiàn)已證明給12個(gè)數(shù)排序最少需要30次比較。我們可以證
明log(n!)的增長(zhǎng)速度與nlogn相同，即log(n!)=Θ(nlogn)。這是排序所需要的最少的比較次數(shù)，它給出了排序復(fù)雜度的一個(gè)下界。
log(n!)=Θ(nlogn)的證明也附在本文最后。
這篇日志 的第
三題中證明log2(N)是最優(yōu)時(shí)用到了幾乎相同的方法。那種“用天平稱出重量不同的那個(gè)球至少要稱幾次”一類題目也可以用這種方法來(lái)解決。事實(shí)上，這里
有一整套的理論，它叫做信息論。信息論是由香農(nóng)(Shannon)提出的。他用對(duì)數(shù)來(lái)表示信息量，用熵來(lái)表示可能的情況的隨機(jī)性，通過(guò)運(yùn)算可以知道你目前
得到的信息能夠怎樣影響最終結(jié)果的確定。如果我們的信息量是以2為底的，那信息論就變成信息學(xué)了。從根本上說(shuō)，計(jì)算機(jī)的一切信息就是以2為底的信息量
(bits=binary digits)，因此我們常說(shuō)香農(nóng)是數(shù)字通信之父。信息論和熱力學(xué)關(guān)系密切，比如熵的概念是直接
從熱力學(xué)的熵定義引申過(guò)來(lái)的。和這個(gè)有關(guān)的東西已經(jīng)嚴(yán)重偏題了，這里不說(shuō)了，有興趣可以去看《信息論與編碼理論》。我對(duì)這個(gè)也很有興趣，半懂不懂的，很想
了解更多的東西，有興趣的同志不妨加入討論。物理學(xué)真的很神奇，利用物理學(xué)可以解決很多純數(shù)學(xué)問(wèn)題，我有時(shí)間的話可以舉一些例子。我他媽的為啥要選文科
呢。
后面將介紹的三種排序是線性時(shí)間復(fù)雜度，因?yàn)椋鼈兣判驎r(shí)根本不是通過(guò)互相比較來(lái)確定大小關(guān)系的。
附
1：Σ(1/n)=Θ(log n)的證明
首先我們證明，Σ(1/n)=O(log
n)。在式子1+1/2+1/3+1/4+1/5+…中，我們把1/3變成1/2，使得兩個(gè)1/2加起來(lái)湊成一個(gè)1；再把1/5,1/6和1/7全部變成
1/4，這樣四個(gè)1/4加起來(lái)又是一個(gè)1。我們把所有1/2^k的后面2^k-1項(xiàng)全部擴(kuò)大為1/2^k，使得這2^k個(gè)分式加起來(lái)是一個(gè)1。現(xiàn)
在，1+1/2+…+1/n里面產(chǎn)生了幾個(gè)1呢？我們只需要看小于n的數(shù)有多少個(gè)2的冪即可。顯然，經(jīng)過(guò)數(shù)的擴(kuò)大后原式各項(xiàng)總和為log
n。O(logn)是Σ(1/n)的復(fù)雜度上界。
然后我們證明，Σ(1/n)=Ω(log
n)。在式子1+1/2+1/3+1/4+1/5+…中，我們把1/3變成1/4，使得兩個(gè)1/4加起來(lái)湊成一個(gè)1/2；再把1/5,1/6和1/7全部
變成1/8，這樣四個(gè)1/8加起來(lái)又是一個(gè)1/2。我們把所有1/2^k的前面2^k-1項(xiàng)全部縮小為1/2^k，使得這2^k個(gè)分式加起來(lái)是一個(gè)1
/2。現(xiàn)在，1+1/2+…+1/n里面產(chǎn)生了幾個(gè)1/2呢？我們只需要看小于n的數(shù)有多少個(gè)2的冪即可。顯然，經(jīng)過(guò)數(shù)的縮小后原式各項(xiàng)總和為1
/2*logn。Ω(logn)是Σ(1/n)的復(fù)雜度下界。
附2：log(n!)=Θ(nlogn)的證明
首
先我們證明，log(n!)=O(nlogn)。顯然n!<n^n，兩邊取對(duì)數(shù)我們得到log(n!)<log(n^n)，而
log(n^n)就等于nlogn。因此，O(nlogn)是log(n!)的復(fù)雜度上界。
然后我們證
明，log(n!)=Ω(nlogn)。n!=n(n-1)(n-2)(n-3)….1，把前面一半的因子全部縮小到n/2，后面一半因子全部舍去，顯然
有n!>(n/2)^(n/2)。兩邊取對(duì)數(shù)，log(n!)>(n/2)log(n/2)，后者即Ω(nlogn)。因
此，Ω(nlogn)是log(n!)的復(fù)雜度下界。
今天寫到這里了，大家?guī)兔π?duì)哦
Matrix67原創(chuàng)
轉(zhuǎn)貼請(qǐng)注明出
處
從零開(kāi)始學(xué)算法：十種排序算法介紹（下）
那么，有什么方法可以不用比較就能排
出順序呢？借助Hash表的思想，多數(shù)人都能想出這樣一種排序算法來(lái)。
我們假設(shè)給出的數(shù)字都在一定范圍中，那么我們就可以開(kāi)一個(gè)范圍相同
的數(shù)組，記錄這個(gè)數(shù)字是否出現(xiàn)過(guò)。由于數(shù)字有可能有重復(fù)，因此Hash表的概念需要擴(kuò)展，我們需要把數(shù)組類型改成整型，用來(lái)表示每個(gè)數(shù)出現(xiàn)的次數(shù)。
看
這樣一個(gè)例子，假如我們要對(duì)數(shù)列3 1 4 1 5 9 2 6 5 3 5
9進(jìn)行排序。由于給定數(shù)字每一個(gè)都小于10，因此我們開(kāi)一個(gè)0到9的整型數(shù)組T[i]，記錄每一個(gè)數(shù)出現(xiàn)了幾次。讀到一個(gè)數(shù)字x，就把對(duì)應(yīng)的T[x]加
一。
A[]= 3, 1, 4, 1, 5, 9, 2, 6,
5, 3, 5, 9
+---+---+---+---+---+---+---+---+---+---+
數(shù)
字 i： | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+---+---+---+---+---+---+---+---+---+---+
出現(xiàn)次數(shù)T[i]： | 0 | 2 | 1 | 2 |
1 | 3 | 1 | 0 | 0 | 2 |
+---+---+---+---+---+---+---+---+---+---+
最后，我們用一個(gè)指針從前
往后掃描一遍，按照次序輸出0到9，每個(gè)數(shù)出現(xiàn)了幾次就輸出幾個(gè)。假如給定的數(shù)是n個(gè)大小不超過(guò)m的自然數(shù)，顯然這個(gè)算法的復(fù)雜度是O(m+n)的。
我
曾經(jīng)以為，這就是線性時(shí)間排序了。后來(lái)我發(fā)現(xiàn)我錯(cuò)了。再后來(lái)，我發(fā)現(xiàn)我曾犯的錯(cuò)誤是一個(gè)普遍的錯(cuò)誤。很多人都以為上面的這個(gè)算法就是傳說(shuō)中的計(jì)數(shù)排序。問(wèn)
題出在哪里了？為什么它不是線性時(shí)間的排序算法？原因是，這個(gè)算法根本不是排序算法，它根本沒(méi)有對(duì)原數(shù)據(jù)進(jìn)行排序。
問(wèn)
題一：為什么說(shuō)上述算法沒(méi)有對(duì)數(shù)據(jù)進(jìn)行排序？
STOP! You
should think for a while.
我們班有很多MM。和身高相差太遠(yuǎn)的MM在一起肯定很別扭，
接個(gè)吻都要彎腰才行（ 小貓 矮死了）。為此，我希望給我們班的MM的身高排序。我們班MM的身高，
再離譜也沒(méi)有超過(guò)2米的，這很適合用我們剛才的算法。我們?cè)诤诎迳袭?huà)一個(gè)100到200的數(shù)組，MM依次自曝身高，我負(fù)責(zé)畫(huà)“正”字統(tǒng)計(jì)人數(shù)。統(tǒng)計(jì)出來(lái)
了，從小到大依次為141, 143, 143, 147, 152, 153,
…。這算哪門子排序？就一排數(shù)字對(duì)我有什么用，我要知道的是哪個(gè)MM有多高。我們僅僅把元素的屬性值從小到大列了出來(lái)，但我們沒(méi)有對(duì)元素本身進(jìn)行排序。也
就是說(shuō)，我們需要知道輸出結(jié)果的每個(gè)數(shù)值對(duì)應(yīng)原數(shù)據(jù)的哪一個(gè)元素。下文提到的“排序算法的穩(wěn)定性”也和屬性值與實(shí)際元素的區(qū)別有關(guān)。
問(wèn)
題二：怎樣將線性時(shí)間排序后的輸出結(jié)果還原為原數(shù)據(jù)中的元素？
STOP!
You should think for a while.
同樣借助Hash表的思想，我們立即想到了類似于
開(kāi)散列的方法。我們用鏈表把屬性值相同的元素串起來(lái)，掛在對(duì)應(yīng)的T[i]上。每次讀到一個(gè)數(shù)，在增加T[i]的同時(shí)我們把這個(gè)元素放進(jìn)T[i]延伸出去的
鏈表里。這樣，輸出結(jié)果時(shí)我們可以方便地獲得原數(shù)據(jù)中的所有屬性值為i的元素。
A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9
+---+---+---+---+---+---+---+---+---+---+
數(shù)字 i： | 0 | 1 | 2 | 3
| 4 | 5 | 6 | 7 | 8 | 9 |
+---+---+---+---+---+---+---+---+---+---+
出現(xiàn)次數(shù)T[i]： | 0 | 2 | 1 | 2 |
1 | 3 | 1 | 0 | 0 | 2 |
+---+o--+-o-+-o-+-o-+-o-+--o+---+---+-o-+
| |
| | | | |
+--+ +-+ | |
+-+ +---+ |
| | A[1] | | |
A[6]
A[2] A[7] | A[3] A[5] A[8] |
| | | A[12]
A[4] A[10] A[9]
|
A[11]
形
象地說(shuō)，我們?cè)诘厣蠑[10個(gè)桶，每個(gè)桶編一個(gè)號(hào)，然后把數(shù)據(jù)分門別類放在自己所屬的桶里。這種排序算法叫做桶式排序(Bucket
Sort)。本文最后你將看到桶式排序的另一個(gè)用途。
鏈表寫起來(lái)比較麻煩，一般我們不使用它。我們有更簡(jiǎn)單的方法。
問(wèn)
題三：同樣是輸出元素本身，你能想出不用鏈表的其它算法么？
STOP!
You should think for a while.
A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9
+---+---+---+---+---+---+---+---+---+---+
數(shù)字 i： | 0 | 1 | 2 | 3
| 4 | 5 | 6 | 7 | 8 | 9 |
+---+---+---+---+---+---+---+---+---+---+
出現(xiàn)次數(shù)T[i]： | 0 | 2 | 1 | 2 |
1 | 3 | 1 | 0 | 0 | 2 |
+---+---+---+---+---+---+---+---+---+---+
修改后的T[i]： | 0 | 2 | 3 | 5 |
6 | 9 | 10| 10| 10| 12|
+---+---+---+---+---+---+---+---+---+---+
所有數(shù)都讀入后，我們修改
T[i]數(shù)組的值，使得T[i]表示數(shù)字i可能的排名的最大值。比如，1最差排名第二，3最遠(yuǎn)可以排到第五。T數(shù)組的最后一個(gè)數(shù)應(yīng)該等于輸入數(shù)據(jù)的數(shù)字個(gè)
數(shù)。修改T數(shù)組的操作可以用一次線性的掃描累加完成。
我們還需要準(zhǔn)備一個(gè)輸出數(shù)組。然后，我們從后往前掃描A數(shù)組，依照T數(shù)組的指示依次
把原數(shù)據(jù)的元素直接放到輸出數(shù)組中，同時(shí)T[i]的值減一。之所以從后往前掃描A數(shù)組，是因?yàn)檫@樣輸出結(jié)果才是穩(wěn)定的。我們說(shuō)一個(gè)排序算法是穩(wěn)定的
(Stable)，當(dāng)算法滿足這樣的性質(zhì)：屬性值相同的元素，排序后前后位置不變，本來(lái)在前面的現(xiàn)在仍然在前面。不要覺(jué)得排序算法是否具有穩(wěn)定性似乎關(guān)系
不大，排序的穩(wěn)定性在下文的某個(gè)問(wèn)題中將變得非常重要。你可以倒回去看看前面說(shuō)的七種排序算法哪些是穩(wěn)定的。
例子中，A數(shù)組最后一個(gè)數(shù)9
所對(duì)應(yīng)的T[9]=12，我們直接把9放在待輸出序列中的第12個(gè)位置，然后T[9]變成11（這樣下一次再出現(xiàn)9時(shí)就應(yīng)該放在第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, 11
Ans
= _ _ _ _ _ _ _ _ _ _ _ 9
接下來(lái)的幾步如下：
A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 <--
T[i]=
0, 2, 3, 5, 6, 8, 10, 10, 10, 11
Ans
= _ _ _ _ _ _ _ _ 5 _ _ 9
A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3
<--
T[i]= 0, 2, 3, 4, 6, 8, 10,
10, 10, 11
Ans = _ _ _ _ 3 _ _ _ 5 _ _ 9
A[]= 3, 1, 4, 1, 5,
9, 2, 6, 5 <--
T[i]= 0, 2, 3, 4, 6, 7,
10, 10, 10, 11
Ans = _ _ _ _ 3 _ _ 5 5 _ _ 9
這種算法叫
做計(jì)數(shù)排序(Counting Sort)。正確性和復(fù)雜度都是顯然的。
問(wèn)題四：給定數(shù)的數(shù)據(jù)范圍大了該怎么
辦？
STOP! You should think for a
while.
前面的算法只有在數(shù)據(jù)的范圍不大時(shí)才可行，如果給定的數(shù)在長(zhǎng)整范圍內(nèi)的話，這個(gè)算法是不可行的，因?yàn)?
你開(kāi)不下這么大的數(shù)組。Radix排序(Radix Sort)解決了這個(gè)難題。
昨天我沒(méi)事翻了一下初中（9班）時(shí)的同學(xué)錄，回憶了一下
過(guò)去。我把比較感興趣的MM的生日列在下面（絕對(duì)真實(shí)）。如果列表中的哪個(gè)MM有幸看到了這篇日志（幾乎不可能），左邊的Support欄有我的電子聯(lián)系
方式，我想知道你們?cè)趺礃恿恕Ｅ琶环窒群蟆?br>
- 19880818
- 19880816
- 19890426
- 19880405
- 19890125
- 19881004
- 19881209
- 19890126
- 19890228
這就是我的數(shù)據(jù)了。現(xiàn)在，我要給這些數(shù)排序。假如我的電腦只能開(kāi)出0..99的數(shù)組，那計(jì)數(shù)排序算法最多對(duì)兩位數(shù)進(jìn)行排序。我就把
每個(gè)八位數(shù)兩位兩位地分成四段（圖1），分別進(jìn)行四次計(jì)數(shù)排序。地球人都知道月份相同時(shí)應(yīng)該看哪一日，因此我們看月份的大小時(shí)應(yīng)該事先保證日已經(jīng)有序。換
句話說(shuō)，我們先對(duì)“最不重要”的部分進(jìn)行排序。我們先對(duì)所有數(shù)的最后兩位進(jìn)行一次計(jì)數(shù)排序（圖2）。注意觀察1月26號(hào)的MM和4月26號(hào)的MM，本次排
序中它們的屬性值相同，由于計(jì)數(shù)排序是穩(wěn)定的，因此4月份那個(gè)排完后依然在1月份那個(gè)的前頭。接下來(lái)我們對(duì)百位和千位進(jìn)行排序（圖3）。你可以看到兩個(gè)
26日的MM在這一次排序中分出了大小，而月份相同的MM依然保持日數(shù)有序（因?yàn)橛?jì)數(shù)排序是穩(wěn)定的）。最后我們對(duì)年份排序（圖4），完成整個(gè)算法。大家都
是跨世紀(jì)的好兒童，因此沒(méi)有圖5了。
這
種算法顯然是正確的。它的復(fù)雜度一般寫成O(d*(n+m))，其中n表示n個(gè)數(shù)，m是我開(kāi)的數(shù)組大小（本例中m=100），d是一個(gè)常數(shù)因子（本例中
d=4）。我們認(rèn)為它也是線性的。
問(wèn)題五：這樣的排序方法還有什么致命的缺陷？
STOP! You should think for a while.
即
使數(shù)據(jù)有30位，我們也可以用d=5或6的Radix算法進(jìn)行排序。但，要是給定的數(shù)據(jù)有無(wú)窮多位怎么辦？有人說(shuō)，這可能么。這是可能的，比如給定的數(shù)據(jù)
是小數(shù)（更準(zhǔn)確地說(shuō)，實(shí)數(shù)）。基于比較的排序可以區(qū)分355/113和π哪
個(gè)大，但你不知道Radix排序需要精確到哪一位。這下慘了，實(shí)數(shù)的出現(xiàn)把貌似高科技的線性時(shí)間排序打回了農(nóng)業(yè)時(shí)代。這時(shí)，桶排序再度出山，挽救了線性時(shí)
間排序悲慘的命運(yùn)。
問(wèn)題六：如何對(duì)實(shí)數(shù)進(jìn)行線性時(shí)間排序？
STOP! You should think for a while.
我
們把問(wèn)題簡(jiǎn)化一下，給出的所有數(shù)都是0到1之間的小數(shù)。如果不是，也可以把所有數(shù)同時(shí)除以一個(gè)大整數(shù)從而轉(zhuǎn)化為這種形式。我們依然設(shè)立若干個(gè)桶，比如，以
小數(shù)點(diǎn)后面一位數(shù)為依據(jù)對(duì)所有數(shù)進(jìn)行劃分。我們?nèi)匀挥面湵戆淹活惖臄?shù)串在一起，不同的是，每一個(gè)鏈表都是有序的。也就是說(shuō)，每一次讀到一個(gè)新的數(shù)都要進(jìn)
行一次插入排序。看我們的例子：
A[]=
0.12345, 0.111, 0.618, 0.9, 0.99999
+---+---+---+---+---+---+---+---+---+---+
十分位： | 0 | 1 | 2 | 3 |
4 | 5 | 6 | 7 | 8 | 9 |
+---+-o-+---+---+---+---+-o-+---+---+-o-+
| | |
A[2]=0.111 A[3]=0.618 A[4]=0.9
| |
A[1]=0.12345 A[5]=0.99999
假如再下一個(gè)讀入的數(shù)是
0.122222，這個(gè)數(shù)需要插入到十分位為1的那個(gè)鏈表里適當(dāng)?shù)奈恢谩Ｎ覀冃枰闅v該鏈表直到找到第一個(gè)比0.122222大的數(shù)，在例子中則應(yīng)該插入
到鏈表中A[2]和A[1]之間。最后，我們按順序遍歷所有鏈表，依次輸出每個(gè)鏈表中的每個(gè)數(shù)。
這個(gè)算法顯然是正確的，但復(fù)雜度顯然不是
線性。事實(shí)上，這種算法最壞情況下是O(n^2)的，因?yàn)楫?dāng)所有數(shù)的十分位都相同時(shí)算法就是一個(gè)插入排序。和原來(lái)一樣，我們下面要計(jì)算算法的平均時(shí)間復(fù)雜
度，我們希望這種算法的平均復(fù)雜度是線性的。
這次算平均復(fù)雜度我們用最笨的辦法。我們將算出所有可能出現(xiàn)的情況的總時(shí)間復(fù)雜度，除以總的
情況數(shù)，得到平均的復(fù)雜度是多少。
每個(gè)數(shù)都可能屬于10個(gè)桶中的一個(gè)，n個(gè)數(shù)總的情況有10^n種。這個(gè)值是我們龐大的算式的分母部分。
如果一個(gè)桶里有K個(gè)元素，那么只與這個(gè)桶有關(guān)的操作有O(K^2)次，它就是一次插入排序的操作次數(shù)。下面計(jì)算，在10^n種情況中，K0=1有多少種情
況。K0=1表示，n個(gè)數(shù)中只有一個(gè)數(shù)在0號(hào)桶，其余n-1個(gè)數(shù)的十分位就只能在1到9中選擇。那么K0=1的情況有C(n,1)*9^(n-1)，而每
個(gè)K0=1的情況在0號(hào)桶中將產(chǎn)生1^2的復(fù)雜度。類似地，Ki=p的情況數(shù)為C(n,p)*9^(n-p)，復(fù)雜度總計(jì)為C(n,p)*9^(n-
p)*p^2。枚舉所有K的下標(biāo)和p值，累加起來(lái)，這個(gè)算式大家應(yīng)該能寫出來(lái)了，但是這個(gè)……怎么算啊。別怕，我們是搞計(jì)算機(jī)的，拿出點(diǎn)和MO不一樣的東
西來(lái)。于是，Mathematica 5.0隆重登場(chǎng)，我做數(shù)學(xué)作業(yè)全靠它。它將幫我們化簡(jiǎn)這個(gè)復(fù)雜的式子。
我
們遺憾地發(fā)現(xiàn)，雖然常數(shù)因子很小（只有0.1），但算法的平均復(fù)雜度仍然是平方的。等一下，1/10的那個(gè)10是我們桶的個(gè)數(shù)嗎？那么我們?yōu)槭裁床话淹暗?
個(gè)數(shù)弄大點(diǎn)？我們干脆用m來(lái)表示桶的個(gè)數(shù)，重新計(jì)算一次：
化
簡(jiǎn)出來(lái)，操作次數(shù)為O(n+n^2/m)。發(fā)現(xiàn)了么，如果m=Θ(n)的話，平均復(fù)雜度就變成了O(n)。也就是說(shuō)，當(dāng)桶的個(gè)數(shù)等于輸入數(shù)據(jù)的個(gè)數(shù)時(shí)，算
法是平均線性的。
我們將在Hash表開(kāi)散列的介紹中重新提到這個(gè)結(jié)論。
且慢，還有一個(gè)問(wèn)題。10個(gè)桶以十分位的
數(shù)字歸類，那么n個(gè)桶用什么方法來(lái)分類呢？注意，分類的方法需要滿足，一，一個(gè)數(shù)分到每個(gè)桶里的概率相同（這樣才有我們上面的結(jié)論）；二，所有桶里容納元
素的范圍必須是連續(xù)的。根據(jù)這兩個(gè)條件，我們有辦法把所有數(shù)恰好分為n類。我們的輸入數(shù)據(jù)不是都在0到1之間么？只需要看這些數(shù)乘以n的整數(shù)部分是多少就
行了，讀到一個(gè)數(shù)后乘以n取整得幾就插入到幾號(hào)桶里。這本質(zhì)上相當(dāng)于把區(qū)間[0,1)平均分成n份。
問(wèn)題七：有
沒(méi)有復(fù)雜度低于線性的排序算法
STOP! You should
think for a while.
我們從O(n^2)走向O(nlogn)，又從O(nlogn)走向線性，
每一次我們都討論了復(fù)雜度下限的問(wèn)題，根據(jù)討論的結(jié)果提出了更優(yōu)的算法。這次總算不行了，不可能有比線性還快的算法了，因?yàn)椤阕x入、輸出數(shù)據(jù)至少就需
要線性的時(shí)間。排序算法之旅在線性時(shí)間復(fù)雜度這一站終止了，所有十種排序算法到這里介紹完畢了。
文章有越寫越長(zhǎng)
的趨勢(shì)了，我檢查起來(lái)也越來(lái)越累了。我又看了三遍，應(yīng)該沒(méi)問(wèn)題了。群眾的眼睛是雪亮的，懇請(qǐng)大家?guī)臀艺义e(cuò)。