九大排序算法再总结
如果要轉(zhuǎn)載，需要注明出處：?http://blog.csdn.net/xiazdong
本文是?http://blog.csdn.net/xiazdong/article/details/7304239?的補(bǔ)充，當(dāng)年看了《大話(huà)數(shù)據(jù)結(jié)構(gòu)》總結(jié)的，但是現(xiàn)在看了《算法導(dǎo)論》，發(fā)現(xiàn)以前對(duì)排序的理解還不深入，所以打算對(duì)各個(gè)排序的思想再整理一遍。 本文首先介紹了基于比較模型的排序算法，即最壞復(fù)雜度都在Ω(nlgn)的排序算法，接著介紹了一些線(xiàn)性時(shí)間排序算法，這些排序算法雖然都在線(xiàn)性時(shí)間，但是都是在對(duì)輸入數(shù)組有一定的約束的前提下才行。 這篇文章參看了《算法導(dǎo)論》第2、3、4、6、7、8章而總結(jié)。
算法的由來(lái)：9世紀(jì)波斯數(shù)學(xué)家提出的：“al-Khowarizmi”
排序的定義： 輸入：n個(gè)數(shù)：a1,a2,a3,...,an 輸出：n個(gè)數(shù)的排列:a1',a2',a3',...,an'，使得a1'<=a2'<=a3'<=...<=an'。
In-place sort（不占用額外內(nèi)存或占用常數(shù)的內(nèi)存）：插入排序、選擇排序、冒泡排序、堆排序、快速排序。 Out-place sort：歸并排序、計(jì)數(shù)排序、基數(shù)排序、桶排序。
當(dāng)需要對(duì)大量數(shù)據(jù)進(jìn)行排序時(shí)，In-place sort就顯示出優(yōu)點(diǎn)，因?yàn)橹恍枰加贸?shù)的內(nèi)存。 設(shè)想一下，如果要對(duì)10000個(gè)數(shù)據(jù)排序，如果使用了Out-place sort，則假設(shè)需要用200G的額外空間，則一臺(tái)老式電腦會(huì)吃不消，但是如果使用In-place sort，則不需要花費(fèi)額外內(nèi)存。
stable sort：插入排序、冒泡排序、歸并排序、計(jì)數(shù)排序、基數(shù)排序、桶排序。 unstable sort：選擇排序(5 8 5 2 9)、快速排序、堆排序。
為何排序的穩(wěn)定性很重要？
在初學(xué)排序時(shí)會(huì)覺(jué)得穩(wěn)定性有這么重要嗎？兩個(gè)一樣的元素的順序有這么重要嗎？其實(shí)很重要。在基數(shù)排序中顯得尤為突出，如下：
算法導(dǎo)論習(xí)題8.3-2說(shuō)：如果對(duì)于不穩(wěn)定的算法進(jìn)行改進(jìn)，使得那些不穩(wěn)定的算法也穩(wěn)定？ 其實(shí)很簡(jiǎn)單，只需要在每個(gè)輸入元素加一個(gè)index，表示初始時(shí)的數(shù)組索引，當(dāng)不穩(wěn)定的算法排好序后，對(duì)于相同的元素對(duì)index排序即可。
基于比較的排序都是遵循“決策樹(shù)模型”，而在決策樹(shù)模型中，我們能證明給予比較的排序算法最壞情況下的運(yùn)行時(shí)間為Ω(nlgn)，證明的思路是因?yàn)閷個(gè)序列構(gòu)成的決策樹(shù)的葉子節(jié)點(diǎn)個(gè)數(shù)至少有n!，因此高度至少為nlgn。
線(xiàn)性時(shí)間排序雖然能夠理想情況下能在線(xiàn)性時(shí)間排序，但是每個(gè)排序都需要對(duì)輸入數(shù)組做一些假設(shè)，比如計(jì)數(shù)排序需要輸入數(shù)組數(shù)字范圍為[0,k]等。
在排序算法的正確性證明中介紹了”循環(huán)不變式“，他類(lèi)似于數(shù)學(xué)歸納法，"初始"對(duì)應(yīng)"n=1"，"保持"對(duì)應(yīng)"假設(shè)n=k成立，當(dāng)n=k+1時(shí)"。
特點(diǎn)：stable sort、In-place sort 最優(yōu)復(fù)雜度：當(dāng)輸入數(shù)組就是排好序的時(shí)候，復(fù)雜度為O(n)，而快速排序在這種情況下會(huì)產(chǎn)生O(n^2)的復(fù)雜度。 最差復(fù)雜度：當(dāng)輸入數(shù)組為倒序時(shí)，復(fù)雜度為O(n^2) 插入排序比較適合用于“少量元素的數(shù)組”。
其實(shí)插入排序的復(fù)雜度和逆序?qū)Φ膫€(gè)數(shù)一樣，當(dāng)數(shù)組倒序時(shí)，逆序?qū)Φ膫€(gè)數(shù)為n(n-1)/2，因此插入排序復(fù)雜度為O(n^2)。 在算法導(dǎo)論2-4中有關(guān)于逆序?qū)Φ慕榻B。
偽代碼：
證明算法正確性：
循環(huán)不變式：在每次循環(huán)開(kāi)始前，A[1...i-1]包含了原來(lái)的A[1...i-1]的元素，并且已排序。
初始：i=2，A[1...1]已排序，成立。 保持：在迭代開(kāi)始前，A[1...i-1]已排序，而循環(huán)體的目的是將A[i]插入A[1...i-1]中，使得A[1...i]排序，因此在下一輪迭代開(kāi) ? ? ? 始前，i++，因此現(xiàn)在A[1...i-1]排好序了，因此保持循環(huán)不變式。 終止：最后i=n+1，并且A[1...n]已排序，而A[1...n]就是整個(gè)數(shù)組，因此證畢。
而在算法導(dǎo)論2.3-6中還問(wèn)是否能將偽代碼第6-8行用二分法實(shí)現(xiàn)？
實(shí)際上是不能的。因?yàn)榈?-8行并不是單純的線(xiàn)性查找，而是還要移出一個(gè)空位讓A[i]插入，因此就算二分查找用O(lgn)查到了插入的位置，但是還是要用O(n)的時(shí)間移出一個(gè)空位。
問(wèn)：快速排序（不使用隨機(jī)化）是否一定比插入排序快？
答：不一定，當(dāng)輸入數(shù)組已經(jīng)排好序時(shí)，插入排序需要O(n)時(shí)間，而快速排序需要O(n^2)時(shí)間。
特點(diǎn)：stable sort、In-place sort 思想：通過(guò)兩兩交換，像水中的泡泡一樣，小的先冒出來(lái)，大的后冒出來(lái)。 最壞運(yùn)行時(shí)間：O(n^2) 最佳運(yùn)行時(shí)間：O(n^2)（當(dāng)然，也可以進(jìn)行改進(jìn)使得最佳運(yùn)行時(shí)間為O(n)）
算法導(dǎo)論思考題2-2中介紹了冒泡排序。
偽代碼：
證明算法正確性：
運(yùn)用兩次循環(huán)不變式，先證明第4-6行的內(nèi)循環(huán)，再證明外循環(huán)。
內(nèi)循環(huán)不變式：在每次循環(huán)開(kāi)始前，A[j]是A[j...n]中最小的元素。
初始：j=n，因此A[n]是A[n...n]的最小元素。 保持：當(dāng)循環(huán)開(kāi)始時(shí)，已知A[j]是A[j...n]的最小元素，將A[j]與A[j-1]比較，并將較小者放在j-1位置，因此能夠說(shuō)明A[j-1]是A[j-1...n]的最小元素，因此循環(huán)不變式保持。 終止：j=i，已知A[i]是A[i...n]中最小的元素，證畢。
接下來(lái)證明外循環(huán)不變式：在每次循環(huán)之前，A[1...i-1]包含了A中最小的i-1個(gè)元素，且已排序：A[1]<=A[2]<=...<=A[i-1]。
初始：i=1，因此A[1..0]=空，因此成立。 保持：當(dāng)循環(huán)開(kāi)始時(shí)，已知A[1...i-1]是A中最小的i-1個(gè)元素，且A[1]<=A[2]<=...<=A[i-1]，根據(jù)內(nèi)循環(huán)不變式，終止時(shí)A[i]是A[i...n]中最小的元素，因此A[1...i]包含了A中最小的i個(gè)元素，且A[1]<=A[2]<=...<=A[i-1]<=A[i] 終止：i=n+1，已知A[1...n]是A中最小的n個(gè)元素，且A[1]<=A[2]<=...<=A[n]，得證。
在算法導(dǎo)論思考題2-2中又問(wèn)了”冒泡排序和插入排序哪個(gè)更快“呢？
一般的人回答：“差不多吧，因?yàn)闈u近時(shí)間都是O(n^2)”。 但是事實(shí)上不是這樣的，插入排序的速度直接是逆序?qū)Φ膫€(gè)數(shù)，而冒泡排序中執(zhí)行“交換“的次數(shù)是逆序?qū)Φ膫€(gè)數(shù)，因此冒泡排序執(zhí)行的時(shí)間至少是逆序?qū)Φ膫€(gè)數(shù)，因此插入排序的執(zhí)行時(shí)間至少比冒泡排序快。
遞歸版冒泡排序
改進(jìn)版冒泡排序
最佳運(yùn)行時(shí)間：O(n) 最壞運(yùn)行時(shí)間：O(n^2)
特性：In-place sort，unstable sort。 思想：每次找一個(gè)最小值。 最好情況時(shí)間：O(n^2)。 最壞情況時(shí)間：O(n^2)。
偽代碼：
證明算法正確性：
循環(huán)不變式：A[1...i-1]包含了A中最小的i-1個(gè)元素，且已排序。
初始：i=1，A[1...0]=空，因此成立。 保持：在某次迭代開(kāi)始之前，保持循環(huán)不變式，即A[1...i-1]包含了A中最小的i-1個(gè)元素，且已排序，則進(jìn)入循環(huán)體后，程序從 ? ? ? ? A[i...n]中找出最小值放在A[i]處，因此A[1...i]包含了A中最小的i個(gè)元素，且已排序，而i++，因此下一次循環(huán)之前，保持 ? ? ? 循環(huán)不變式：A[1..i-1]包含了A中最小的i-1個(gè)元素，且已排序。 終止：i=n，已知A[1...n-1]包含了A中最小的i-1個(gè)元素，且已排序，因此A[n]中的元素是最大的，因此A[1...n]已排序，證畢。
算法導(dǎo)論2.2-2中問(wèn)了"為什么偽代碼中第3行只有循環(huán)n-1次而不是n次"？
在循環(huán)不變式證明中也提到了，如果A[1...n-1]已排序，且包含了A中最小的n-1個(gè)元素，則A[n]肯定是最大的，因此肯定是已排序的。
遞歸版選擇排序
遞歸式：
T(n)=T(n-1)+O(n)? => T(n)=O(n^2)
特點(diǎn)：stable sort、Out-place sort 思想：運(yùn)用分治法思想解決排序問(wèn)題。 最壞情況運(yùn)行時(shí)間：O(nlgn) 最佳運(yùn)行時(shí)間：O(nlgn)
分治法介紹：分治法就是將原問(wèn)題分解為多個(gè)獨(dú)立的子問(wèn)題，且這些子問(wèn)題的形式和原問(wèn)題相似，只是規(guī)模上減少了，求解完子問(wèn)題后合并結(jié)果構(gòu)成原問(wèn)題的解。 分治法通常有3步：Divide（分解子問(wèn)題的步驟） 、 Conquer（遞歸解決子問(wèn)題的步驟）、 Combine（子問(wèn)題解求出來(lái)后合并成原問(wèn)題解的步驟）。 假設(shè)Divide需要f(n)時(shí)間，Conquer分解為b個(gè)子問(wèn)題，且子問(wèn)題大小為a，Combine需要g(n)時(shí)間，則遞歸式為： T(n)=bT(n/a)+f(n)+g(n)
算法導(dǎo)論思考題4-3（參數(shù)傳遞）能夠很好的考察對(duì)于分治法的理解。
就如歸并排序，Divide的步驟為m=(p+q)/2，因此為O(1)，Combine步驟為merge()函數(shù)，Conquer步驟為分解為2個(gè)子問(wèn)題，子問(wèn)題大小為n/2，因此： 歸并排序的遞歸式：T(n)=2T(n/2)+O(n)
而求解遞歸式的三種方法有： (1)替換法：主要用于驗(yàn)證遞歸式的復(fù)雜度。 (2)遞歸樹(shù)：能夠大致估算遞歸式的復(fù)雜度，估算完后可以用替換法驗(yàn)證。 (3)主定理：用于解一些常見(jiàn)的遞歸式。
偽代碼：
證明算法正確性：
其實(shí)我們只要證明merge()函數(shù)的正確性即可。 merge函數(shù)的主要步驟在第25~31行，可以看出是由一個(gè)循環(huán)構(gòu)成。
循環(huán)不變式：每次循環(huán)之前，A[p...k-1]已排序，且L[i]和R[j]是L和R中剩下的元素中最小的兩個(gè)元素。 初始：k=p，A[p...p-1]為空，因此已排序，成立。 保持：在第k次迭代之前，A[p...k-1]已經(jīng)排序，而因?yàn)長(zhǎng)[i]和R[j]是L和R中剩下的元素中最小的兩個(gè)元素，因此只需要將L[i]和R[j]中最小的元素放到A[k]即可，在第k+1次迭代之前A[p...k]已排序，且L[i]和R[j]為剩下的最小的兩個(gè)元素。 終止：k=q+1，且A[p...q]已排序，這就是我們想要的，因此證畢。
歸并排序的例子：
問(wèn)：歸并排序的缺點(diǎn)是什么？
答：他是Out-place sort，因此相比快排，需要很多額外的空間。
問(wèn)：為什么歸并排序比快速排序慢？
答：雖然漸近復(fù)雜度一樣，但是歸并排序的系數(shù)比快排大。
問(wèn)：對(duì)于歸并排序有什么改進(jìn)？
答：就是在數(shù)組長(zhǎng)度為k時(shí)，用插入排序，因?yàn)椴迦肱判蜻m合對(duì)小數(shù)組排序。在算法導(dǎo)論思考題2-1中介紹了。復(fù)雜度為O(nk+nlg(n/k)) ，當(dāng)k=O(lgn)時(shí)，復(fù)雜度為O(nlgn)
Tony Hoare爵士在1962年發(fā)明，被譽(yù)為“20世紀(jì)十大經(jīng)典算法之一”。 算法導(dǎo)論中講解的快速排序的PARTITION是Lomuto提出的，是對(duì)Hoare的算法進(jìn)行一些改變的，而算法導(dǎo)論7-1介紹了Hoare的快排。 特性：unstable sort、In-place sort。 最壞運(yùn)行時(shí)間：當(dāng)輸入數(shù)組已排序時(shí)，時(shí)間為O(n^2)，當(dāng)然可以通過(guò)隨機(jī)化來(lái)改進(jìn)（shuffle array 或者 randomized select pivot）,使得期望運(yùn)行時(shí)間為O(nlgn)。 最佳運(yùn)行時(shí)間：O(nlgn) 快速排序的思想也是分治法。 當(dāng)輸入數(shù)組的所有元素都一樣時(shí)，不管是快速排序還是隨機(jī)化快速排序的復(fù)雜度都為O(n^2)，而在算法導(dǎo)論第三版的思考題7-2中通過(guò)改變Partition函數(shù)，從而改進(jìn)復(fù)雜度為O(n)。
注意：只要partition的劃分比例是常數(shù)的，則快排的效率就是O(nlgn)，比如當(dāng)partition的劃分比例為10000:1時(shí)（足夠不平衡了），快排的效率還是O(nlgn)
“A killer adversary for quicksort”這篇文章很有趣的介紹了怎么樣設(shè)計(jì)一個(gè)輸入數(shù)組，使得quicksort運(yùn)行時(shí)間為O(n^2)。
偽代碼：
隨機(jī)化partition的實(shí)現(xiàn)：
改進(jìn)當(dāng)所有元素相同時(shí)的效率的Partition實(shí)現(xiàn)：
證明算法正確性：
對(duì)partition函數(shù)證明循環(huán)不變式：A[p...i]的所有元素小于等于pivot，A[i+1...j-1]的所有元素大于pivot。 初始：i=p-1,j=p，因此A[p...p-1]=空，A[p...p-1]=空，因此成立。 保持：當(dāng)循環(huán)開(kāi)始前，已知A[p...i]的所有元素小于等于pivot，A[i+1...j-1]的所有元素大于pivot，在循環(huán)體中， ????????? ? -?如果A[j]>pivot，那么不動(dòng)，j++，此時(shí)A[p...i]的所有元素小于等于pivot，A[i+1...j-1]的所有元素大于pivot。 ??????? ? ??- 如果A[j]<=pivot，則i++，A[i+1]>pivot，將A[i+1]和A[j]交換后，A[P...i]保持所有元素小于等于pivot，而A[i+1...j-1]的所有元素大于pivot。 終止：j=r，因此A[p...i]的所有元素小于等于pivot，A[i+1...r-1]的所有元素大于pivot。
1964年Williams提出。
特性：unstable sort、In-place sort。 最優(yōu)時(shí)間：O(nlgn) 最差時(shí)間：O(nlgn) 此篇文章介紹了堆排序的最優(yōu)時(shí)間和最差時(shí)間的證明：http://blog.csdn.net/xiazdong/article/details/8193625? 思想：運(yùn)用了最小堆、最大堆這個(gè)數(shù)據(jù)結(jié)構(gòu)，而堆還能用于構(gòu)建優(yōu)先隊(duì)列。
優(yōu)先隊(duì)列應(yīng)用于進(jìn)程間調(diào)度、任務(wù)調(diào)度等。 堆數(shù)據(jù)結(jié)構(gòu)應(yīng)用于Dijkstra、Prim算法。
證明算法正確性：
（1）證明build_max_heap的正確性： 循環(huán)不變式：每次循環(huán)開(kāi)始前，A[i+1]、A[i+2]、...、A[n]分別為最大堆的根。
初始：i=floor(n/2)，則A[i+1]、...、A[n]都是葉子，因此成立。 保持：每次迭代開(kāi)始前，已知A[i+1]、A[i+2]、...、A[n]分別為最大堆的根，在循環(huán)體中，因?yàn)锳[i]的孩子的子樹(shù)都是最大堆，因此執(zhí)行完MAX_HEAPIFY(A,i)后，A[i]也是最大堆的根，因此保持循環(huán)不變式。 終止：i=0，已知A[1]、...、A[n]都是最大堆的根，得到了A[1]是最大堆的根，因此證畢。
（2）證明heapsort的正確性： 循環(huán)不變式：每次迭代前，A[i+1]、...、A[n]包含了A中最大的n-i個(gè)元素，且A[i+1]<=A[i+2]<=...<=A[n]，且A[1]是堆中最大的。
初始：i=n，A[n+1]...A[n]為空，成立。 保持：每次迭代開(kāi)始前，A[i+1]、...、A[n]包含了A中最大的n-i個(gè)元素，且A[i+1]<=A[i+2]<=...<=A[n]，循環(huán)體內(nèi)將A[1]與A[i]交換，因?yàn)锳[1]是堆中最大的，因此A[i]、...、A[n]包含了A中最大的n-i+1個(gè)元素且A[i]<=A[i+1]<=A[i+2]<=...<=A[n]，因此保持循環(huán)不變式。 終止：i=1，已知A[2]、...、A[n]包含了A中最大的n-1個(gè)元素，且A[2]<=A[3]<=...<=A[n]，因此A[1]<=A[2]<=A[3]<=...<=A[n]，證畢。
特性：stable sort、out-place sort。 最壞情況運(yùn)行時(shí)間：O(n+k) 最好情況運(yùn)行時(shí)間：O(n+k)
當(dāng)k=O(n)時(shí)，計(jì)數(shù)排序時(shí)間為O(n)
偽代碼：
本文假定每位的排序是計(jì)數(shù)排序。 特性：stable sort、Out-place sort。 最壞情況運(yùn)行時(shí)間：O((n+k)d) 最好情況運(yùn)行時(shí)間：O((n+k)d)
當(dāng)d為常數(shù)、k=O(n)時(shí)，效率為O(n) 我們也不一定要一位一位排序，我們可以多位多位排序，比如一共10位，我們可以先對(duì)低5位排序，再對(duì)高5位排序。 引理：假設(shè)n個(gè)b位數(shù)，將b位數(shù)分為多個(gè)單元，且每個(gè)單元為r位，那么基數(shù)排序的效率為O[(b/r)(n+2^r)]。 當(dāng)b=O(nlgn)，r=lgn時(shí)，基數(shù)排序效率O(n)
比如算法導(dǎo)論習(xí)題8.3-4：說(shuō)明如何在O(n)時(shí)間內(nèi)，對(duì)0~n^2-1之間的n個(gè)整數(shù)排序？ 答案：將這些數(shù)化為2進(jìn)制，位數(shù)為lg(n^2)=2lgn=O(lgn)，因此利用引理，b=O(lgn)，而我們?cè)O(shè)r=lgn，則基數(shù)排序可以在O(n)內(nèi)排序。
基數(shù)排序的例子：
證明算法正確性：
通過(guò)循環(huán)不變式可證，證明略。
假設(shè)輸入數(shù)組的元素都在[0,1)之間。 特性：out-place sort、stable sort。 最壞情況運(yùn)行時(shí)間：當(dāng)分布不均勻時(shí)，全部元素都分到一個(gè)桶中，則O(n^2)，當(dāng)然[算法導(dǎo)論8.4-2]也可以將插入排序換成堆排序、快速排序等，這樣最壞情況就是O(nlgn)。 最好情況運(yùn)行時(shí)間：O(n)
桶排序的例子：
偽代碼：
證明算法正確性：
對(duì)于任意A[i]<=A[j]，且A[i]落在B[a]，A[j]落在B[b]，我們可以看出a<=b，因此得證。
本文是?http://blog.csdn.net/xiazdong/article/details/7304239?的補(bǔ)充，當(dāng)年看了《大話(huà)數(shù)據(jù)結(jié)構(gòu)》總結(jié)的，但是現(xiàn)在看了《算法導(dǎo)論》，發(fā)現(xiàn)以前對(duì)排序的理解還不深入，所以打算對(duì)各個(gè)排序的思想再整理一遍。 本文首先介紹了基于比較模型的排序算法，即最壞復(fù)雜度都在Ω(nlgn)的排序算法，接著介紹了一些線(xiàn)性時(shí)間排序算法，這些排序算法雖然都在線(xiàn)性時(shí)間，但是都是在對(duì)輸入數(shù)組有一定的約束的前提下才行。 這篇文章參看了《算法導(dǎo)論》第2、3、4、6、7、8章而總結(jié)。
算法的由來(lái)：9世紀(jì)波斯數(shù)學(xué)家提出的：“al-Khowarizmi”
排序的定義： 輸入：n個(gè)數(shù)：a1,a2,a3,...,an 輸出：n個(gè)數(shù)的排列:a1',a2',a3',...,an'，使得a1'<=a2'<=a3'<=...<=an'。
In-place sort（不占用額外內(nèi)存或占用常數(shù)的內(nèi)存）：插入排序、選擇排序、冒泡排序、堆排序、快速排序。 Out-place sort：歸并排序、計(jì)數(shù)排序、基數(shù)排序、桶排序。
當(dāng)需要對(duì)大量數(shù)據(jù)進(jìn)行排序時(shí)，In-place sort就顯示出優(yōu)點(diǎn)，因?yàn)橹恍枰加贸?shù)的內(nèi)存。 設(shè)想一下，如果要對(duì)10000個(gè)數(shù)據(jù)排序，如果使用了Out-place sort，則假設(shè)需要用200G的額外空間，則一臺(tái)老式電腦會(huì)吃不消，但是如果使用In-place sort，則不需要花費(fèi)額外內(nèi)存。
stable sort：插入排序、冒泡排序、歸并排序、計(jì)數(shù)排序、基數(shù)排序、桶排序。 unstable sort：選擇排序(5 8 5 2 9)、快速排序、堆排序。
為何排序的穩(wěn)定性很重要？
在初學(xué)排序時(shí)會(huì)覺(jué)得穩(wěn)定性有這么重要嗎？兩個(gè)一樣的元素的順序有這么重要嗎？其實(shí)很重要。在基數(shù)排序中顯得尤為突出，如下：
算法導(dǎo)論習(xí)題8.3-2說(shuō)：如果對(duì)于不穩(wěn)定的算法進(jìn)行改進(jìn)，使得那些不穩(wěn)定的算法也穩(wěn)定？ 其實(shí)很簡(jiǎn)單，只需要在每個(gè)輸入元素加一個(gè)index，表示初始時(shí)的數(shù)組索引，當(dāng)不穩(wěn)定的算法排好序后，對(duì)于相同的元素對(duì)index排序即可。
基于比較的排序都是遵循“決策樹(shù)模型”，而在決策樹(shù)模型中，我們能證明給予比較的排序算法最壞情況下的運(yùn)行時(shí)間為Ω(nlgn)，證明的思路是因?yàn)閷個(gè)序列構(gòu)成的決策樹(shù)的葉子節(jié)點(diǎn)個(gè)數(shù)至少有n!，因此高度至少為nlgn。
線(xiàn)性時(shí)間排序雖然能夠理想情況下能在線(xiàn)性時(shí)間排序，但是每個(gè)排序都需要對(duì)輸入數(shù)組做一些假設(shè)，比如計(jì)數(shù)排序需要輸入數(shù)組數(shù)字范圍為[0,k]等。
在排序算法的正確性證明中介紹了”循環(huán)不變式“，他類(lèi)似于數(shù)學(xué)歸納法，"初始"對(duì)應(yīng)"n=1"，"保持"對(duì)應(yīng)"假設(shè)n=k成立，當(dāng)n=k+1時(shí)"。
一、插入排序
特點(diǎn)：stable sort、In-place sort 最優(yōu)復(fù)雜度：當(dāng)輸入數(shù)組就是排好序的時(shí)候，復(fù)雜度為O(n)，而快速排序在這種情況下會(huì)產(chǎn)生O(n^2)的復(fù)雜度。 最差復(fù)雜度：當(dāng)輸入數(shù)組為倒序時(shí)，復(fù)雜度為O(n^2) 插入排序比較適合用于“少量元素的數(shù)組”。
其實(shí)插入排序的復(fù)雜度和逆序?qū)Φ膫€(gè)數(shù)一樣，當(dāng)數(shù)組倒序時(shí)，逆序?qū)Φ膫€(gè)數(shù)為n(n-1)/2，因此插入排序復(fù)雜度為O(n^2)。 在算法導(dǎo)論2-4中有關(guān)于逆序?qū)Φ慕榻B。
偽代碼：
證明算法正確性：
循環(huán)不變式：在每次循環(huán)開(kāi)始前，A[1...i-1]包含了原來(lái)的A[1...i-1]的元素，并且已排序。
初始：i=2，A[1...1]已排序，成立。 保持：在迭代開(kāi)始前，A[1...i-1]已排序，而循環(huán)體的目的是將A[i]插入A[1...i-1]中，使得A[1...i]排序，因此在下一輪迭代開(kāi) ? ? ? 始前，i++，因此現(xiàn)在A[1...i-1]排好序了，因此保持循環(huán)不變式。 終止：最后i=n+1，并且A[1...n]已排序，而A[1...n]就是整個(gè)數(shù)組，因此證畢。
而在算法導(dǎo)論2.3-6中還問(wèn)是否能將偽代碼第6-8行用二分法實(shí)現(xiàn)？
實(shí)際上是不能的。因?yàn)榈?-8行并不是單純的線(xiàn)性查找，而是還要移出一個(gè)空位讓A[i]插入，因此就算二分查找用O(lgn)查到了插入的位置，但是還是要用O(n)的時(shí)間移出一個(gè)空位。
問(wèn)：快速排序（不使用隨機(jī)化）是否一定比插入排序快？
答：不一定，當(dāng)輸入數(shù)組已經(jīng)排好序時(shí)，插入排序需要O(n)時(shí)間，而快速排序需要O(n^2)時(shí)間。
遞歸版插入排序
二、冒泡排序
特點(diǎn)：stable sort、In-place sort 思想：通過(guò)兩兩交換，像水中的泡泡一樣，小的先冒出來(lái)，大的后冒出來(lái)。 最壞運(yùn)行時(shí)間：O(n^2) 最佳運(yùn)行時(shí)間：O(n^2)（當(dāng)然，也可以進(jìn)行改進(jìn)使得最佳運(yùn)行時(shí)間為O(n)）
算法導(dǎo)論思考題2-2中介紹了冒泡排序。
偽代碼：
證明算法正確性：
運(yùn)用兩次循環(huán)不變式，先證明第4-6行的內(nèi)循環(huán)，再證明外循環(huán)。
內(nèi)循環(huán)不變式：在每次循環(huán)開(kāi)始前，A[j]是A[j...n]中最小的元素。
初始：j=n，因此A[n]是A[n...n]的最小元素。 保持：當(dāng)循環(huán)開(kāi)始時(shí)，已知A[j]是A[j...n]的最小元素，將A[j]與A[j-1]比較，并將較小者放在j-1位置，因此能夠說(shuō)明A[j-1]是A[j-1...n]的最小元素，因此循環(huán)不變式保持。 終止：j=i，已知A[i]是A[i...n]中最小的元素，證畢。
接下來(lái)證明外循環(huán)不變式：在每次循環(huán)之前，A[1...i-1]包含了A中最小的i-1個(gè)元素，且已排序：A[1]<=A[2]<=...<=A[i-1]。
初始：i=1，因此A[1..0]=空，因此成立。 保持：當(dāng)循環(huán)開(kāi)始時(shí)，已知A[1...i-1]是A中最小的i-1個(gè)元素，且A[1]<=A[2]<=...<=A[i-1]，根據(jù)內(nèi)循環(huán)不變式，終止時(shí)A[i]是A[i...n]中最小的元素，因此A[1...i]包含了A中最小的i個(gè)元素，且A[1]<=A[2]<=...<=A[i-1]<=A[i] 終止：i=n+1，已知A[1...n]是A中最小的n個(gè)元素，且A[1]<=A[2]<=...<=A[n]，得證。
在算法導(dǎo)論思考題2-2中又問(wèn)了”冒泡排序和插入排序哪個(gè)更快“呢？
一般的人回答：“差不多吧，因?yàn)闈u近時(shí)間都是O(n^2)”。 但是事實(shí)上不是這樣的，插入排序的速度直接是逆序?qū)Φ膫€(gè)數(shù)，而冒泡排序中執(zhí)行“交換“的次數(shù)是逆序?qū)Φ膫€(gè)數(shù)，因此冒泡排序執(zhí)行的時(shí)間至少是逆序?qū)Φ膫€(gè)數(shù)，因此插入排序的執(zhí)行時(shí)間至少比冒泡排序快。
遞歸版冒泡排序
改進(jìn)版冒泡排序
最佳運(yùn)行時(shí)間：O(n) 最壞運(yùn)行時(shí)間：O(n^2)
三、選擇排序
特性：In-place sort，unstable sort。 思想：每次找一個(gè)最小值。 最好情況時(shí)間：O(n^2)。 最壞情況時(shí)間：O(n^2)。
偽代碼：
證明算法正確性：
循環(huán)不變式：A[1...i-1]包含了A中最小的i-1個(gè)元素，且已排序。
初始：i=1，A[1...0]=空，因此成立。 保持：在某次迭代開(kāi)始之前，保持循環(huán)不變式，即A[1...i-1]包含了A中最小的i-1個(gè)元素，且已排序，則進(jìn)入循環(huán)體后，程序從 ? ? ? ? A[i...n]中找出最小值放在A[i]處，因此A[1...i]包含了A中最小的i個(gè)元素，且已排序，而i++，因此下一次循環(huán)之前，保持 ? ? ? 循環(huán)不變式：A[1..i-1]包含了A中最小的i-1個(gè)元素，且已排序。 終止：i=n，已知A[1...n-1]包含了A中最小的i-1個(gè)元素，且已排序，因此A[n]中的元素是最大的，因此A[1...n]已排序，證畢。
算法導(dǎo)論2.2-2中問(wèn)了"為什么偽代碼中第3行只有循環(huán)n-1次而不是n次"？
在循環(huán)不變式證明中也提到了，如果A[1...n-1]已排序，且包含了A中最小的n-1個(gè)元素，則A[n]肯定是最大的，因此肯定是已排序的。
遞歸版選擇排序
遞歸式：
T(n)=T(n-1)+O(n)? => T(n)=O(n^2)
四、歸并排序
特點(diǎn)：stable sort、Out-place sort 思想：運(yùn)用分治法思想解決排序問(wèn)題。 最壞情況運(yùn)行時(shí)間：O(nlgn) 最佳運(yùn)行時(shí)間：O(nlgn)
分治法介紹：分治法就是將原問(wèn)題分解為多個(gè)獨(dú)立的子問(wèn)題，且這些子問(wèn)題的形式和原問(wèn)題相似，只是規(guī)模上減少了，求解完子問(wèn)題后合并結(jié)果構(gòu)成原問(wèn)題的解。 分治法通常有3步：Divide（分解子問(wèn)題的步驟） 、 Conquer（遞歸解決子問(wèn)題的步驟）、 Combine（子問(wèn)題解求出來(lái)后合并成原問(wèn)題解的步驟）。 假設(shè)Divide需要f(n)時(shí)間，Conquer分解為b個(gè)子問(wèn)題，且子問(wèn)題大小為a，Combine需要g(n)時(shí)間，則遞歸式為： T(n)=bT(n/a)+f(n)+g(n)
算法導(dǎo)論思考題4-3（參數(shù)傳遞）能夠很好的考察對(duì)于分治法的理解。
就如歸并排序，Divide的步驟為m=(p+q)/2，因此為O(1)，Combine步驟為merge()函數(shù)，Conquer步驟為分解為2個(gè)子問(wèn)題，子問(wèn)題大小為n/2，因此： 歸并排序的遞歸式：T(n)=2T(n/2)+O(n)
而求解遞歸式的三種方法有： (1)替換法：主要用于驗(yàn)證遞歸式的復(fù)雜度。 (2)遞歸樹(shù)：能夠大致估算遞歸式的復(fù)雜度，估算完后可以用替換法驗(yàn)證。 (3)主定理：用于解一些常見(jiàn)的遞歸式。
偽代碼：
證明算法正確性：
其實(shí)我們只要證明merge()函數(shù)的正確性即可。 merge函數(shù)的主要步驟在第25~31行，可以看出是由一個(gè)循環(huán)構(gòu)成。
循環(huán)不變式：每次循環(huán)之前，A[p...k-1]已排序，且L[i]和R[j]是L和R中剩下的元素中最小的兩個(gè)元素。 初始：k=p，A[p...p-1]為空，因此已排序，成立。 保持：在第k次迭代之前，A[p...k-1]已經(jīng)排序，而因?yàn)長(zhǎng)[i]和R[j]是L和R中剩下的元素中最小的兩個(gè)元素，因此只需要將L[i]和R[j]中最小的元素放到A[k]即可，在第k+1次迭代之前A[p...k]已排序，且L[i]和R[j]為剩下的最小的兩個(gè)元素。 終止：k=q+1，且A[p...q]已排序，這就是我們想要的，因此證畢。
歸并排序的例子：
問(wèn)：歸并排序的缺點(diǎn)是什么？
答：他是Out-place sort，因此相比快排，需要很多額外的空間。
問(wèn)：為什么歸并排序比快速排序慢？
答：雖然漸近復(fù)雜度一樣，但是歸并排序的系數(shù)比快排大。
問(wèn)：對(duì)于歸并排序有什么改進(jìn)？
答：就是在數(shù)組長(zhǎng)度為k時(shí)，用插入排序，因?yàn)椴迦肱判蜻m合對(duì)小數(shù)組排序。在算法導(dǎo)論思考題2-1中介紹了。復(fù)雜度為O(nk+nlg(n/k)) ，當(dāng)k=O(lgn)時(shí)，復(fù)雜度為O(nlgn)
五、快速排序
Tony Hoare爵士在1962年發(fā)明，被譽(yù)為“20世紀(jì)十大經(jīng)典算法之一”。 算法導(dǎo)論中講解的快速排序的PARTITION是Lomuto提出的，是對(duì)Hoare的算法進(jìn)行一些改變的，而算法導(dǎo)論7-1介紹了Hoare的快排。 特性：unstable sort、In-place sort。 最壞運(yùn)行時(shí)間：當(dāng)輸入數(shù)組已排序時(shí)，時(shí)間為O(n^2)，當(dāng)然可以通過(guò)隨機(jī)化來(lái)改進(jìn)（shuffle array 或者 randomized select pivot）,使得期望運(yùn)行時(shí)間為O(nlgn)。 最佳運(yùn)行時(shí)間：O(nlgn) 快速排序的思想也是分治法。 當(dāng)輸入數(shù)組的所有元素都一樣時(shí)，不管是快速排序還是隨機(jī)化快速排序的復(fù)雜度都為O(n^2)，而在算法導(dǎo)論第三版的思考題7-2中通過(guò)改變Partition函數(shù)，從而改進(jìn)復(fù)雜度為O(n)。
注意：只要partition的劃分比例是常數(shù)的，則快排的效率就是O(nlgn)，比如當(dāng)partition的劃分比例為10000:1時(shí)（足夠不平衡了），快排的效率還是O(nlgn)
“A killer adversary for quicksort”這篇文章很有趣的介紹了怎么樣設(shè)計(jì)一個(gè)輸入數(shù)組，使得quicksort運(yùn)行時(shí)間為O(n^2)。
偽代碼：
隨機(jī)化partition的實(shí)現(xiàn)：
改進(jìn)當(dāng)所有元素相同時(shí)的效率的Partition實(shí)現(xiàn)：
證明算法正確性：
對(duì)partition函數(shù)證明循環(huán)不變式：A[p...i]的所有元素小于等于pivot，A[i+1...j-1]的所有元素大于pivot。 初始：i=p-1,j=p，因此A[p...p-1]=空，A[p...p-1]=空，因此成立。 保持：當(dāng)循環(huán)開(kāi)始前，已知A[p...i]的所有元素小于等于pivot，A[i+1...j-1]的所有元素大于pivot，在循環(huán)體中， ????????? ? -?如果A[j]>pivot，那么不動(dòng)，j++，此時(shí)A[p...i]的所有元素小于等于pivot，A[i+1...j-1]的所有元素大于pivot。 ??????? ? ??- 如果A[j]<=pivot，則i++，A[i+1]>pivot，將A[i+1]和A[j]交換后，A[P...i]保持所有元素小于等于pivot，而A[i+1...j-1]的所有元素大于pivot。 終止：j=r，因此A[p...i]的所有元素小于等于pivot，A[i+1...r-1]的所有元素大于pivot。
六、堆排序
1964年Williams提出。
特性：unstable sort、In-place sort。 最優(yōu)時(shí)間：O(nlgn) 最差時(shí)間：O(nlgn) 此篇文章介紹了堆排序的最優(yōu)時(shí)間和最差時(shí)間的證明：http://blog.csdn.net/xiazdong/article/details/8193625? 思想：運(yùn)用了最小堆、最大堆這個(gè)數(shù)據(jù)結(jié)構(gòu)，而堆還能用于構(gòu)建優(yōu)先隊(duì)列。
優(yōu)先隊(duì)列應(yīng)用于進(jìn)程間調(diào)度、任務(wù)調(diào)度等。 堆數(shù)據(jù)結(jié)構(gòu)應(yīng)用于Dijkstra、Prim算法。
證明算法正確性：
（1）證明build_max_heap的正確性： 循環(huán)不變式：每次循環(huán)開(kāi)始前，A[i+1]、A[i+2]、...、A[n]分別為最大堆的根。
初始：i=floor(n/2)，則A[i+1]、...、A[n]都是葉子，因此成立。 保持：每次迭代開(kāi)始前，已知A[i+1]、A[i+2]、...、A[n]分別為最大堆的根，在循環(huán)體中，因?yàn)锳[i]的孩子的子樹(shù)都是最大堆，因此執(zhí)行完MAX_HEAPIFY(A,i)后，A[i]也是最大堆的根，因此保持循環(huán)不變式。 終止：i=0，已知A[1]、...、A[n]都是最大堆的根，得到了A[1]是最大堆的根，因此證畢。
（2）證明heapsort的正確性： 循環(huán)不變式：每次迭代前，A[i+1]、...、A[n]包含了A中最大的n-i個(gè)元素，且A[i+1]<=A[i+2]<=...<=A[n]，且A[1]是堆中最大的。
初始：i=n，A[n+1]...A[n]為空，成立。 保持：每次迭代開(kāi)始前，A[i+1]、...、A[n]包含了A中最大的n-i個(gè)元素，且A[i+1]<=A[i+2]<=...<=A[n]，循環(huán)體內(nèi)將A[1]與A[i]交換，因?yàn)锳[1]是堆中最大的，因此A[i]、...、A[n]包含了A中最大的n-i+1個(gè)元素且A[i]<=A[i+1]<=A[i+2]<=...<=A[n]，因此保持循環(huán)不變式。 終止：i=1，已知A[2]、...、A[n]包含了A中最大的n-1個(gè)元素，且A[2]<=A[3]<=...<=A[n]，因此A[1]<=A[2]<=A[3]<=...<=A[n]，證畢。
七、計(jì)數(shù)排序
特性：stable sort、out-place sort。 最壞情況運(yùn)行時(shí)間：O(n+k) 最好情況運(yùn)行時(shí)間：O(n+k)
當(dāng)k=O(n)時(shí)，計(jì)數(shù)排序時(shí)間為O(n)
偽代碼：
八、基數(shù)排序
本文假定每位的排序是計(jì)數(shù)排序。 特性：stable sort、Out-place sort。 最壞情況運(yùn)行時(shí)間：O((n+k)d) 最好情況運(yùn)行時(shí)間：O((n+k)d)
當(dāng)d為常數(shù)、k=O(n)時(shí)，效率為O(n) 我們也不一定要一位一位排序，我們可以多位多位排序，比如一共10位，我們可以先對(duì)低5位排序，再對(duì)高5位排序。 引理：假設(shè)n個(gè)b位數(shù)，將b位數(shù)分為多個(gè)單元，且每個(gè)單元為r位，那么基數(shù)排序的效率為O[(b/r)(n+2^r)]。 當(dāng)b=O(nlgn)，r=lgn時(shí)，基數(shù)排序效率O(n)
比如算法導(dǎo)論習(xí)題8.3-4：說(shuō)明如何在O(n)時(shí)間內(nèi)，對(duì)0~n^2-1之間的n個(gè)整數(shù)排序？ 答案：將這些數(shù)化為2進(jìn)制，位數(shù)為lg(n^2)=2lgn=O(lgn)，因此利用引理，b=O(lgn)，而我們?cè)O(shè)r=lgn，則基數(shù)排序可以在O(n)內(nèi)排序。
基數(shù)排序的例子：
證明算法正確性：
通過(guò)循環(huán)不變式可證，證明略。
九、桶排序
假設(shè)輸入數(shù)組的元素都在[0,1)之間。 特性：out-place sort、stable sort。 最壞情況運(yùn)行時(shí)間：當(dāng)分布不均勻時(shí)，全部元素都分到一個(gè)桶中，則O(n^2)，當(dāng)然[算法導(dǎo)論8.4-2]也可以將插入排序換成堆排序、快速排序等，這樣最壞情況就是O(nlgn)。 最好情況運(yùn)行時(shí)間：O(n)
桶排序的例子：
偽代碼：
證明算法正確性：
對(duì)于任意A[i]<=A[j]，且A[i]落在B[a]，A[j]落在B[b]，我們可以看出a<=b，因此得證。
總結(jié)
