轉載出處：?http://blog.csdn.net/xiazdong

本文是?http://blog.csdn.net/xiazdong/article/details/7304239?的補充，當年看了《大話數據結構》總結的，但是現在看了《算法導論》，發現以前對排序的理解還不深入，所以打算對各個排序的思想再整理一遍。 本文首先介紹了基于比較模型的排序算法，即最壞復雜度都在Ω(nlgn)的排序算法，接著介紹了一些線性時間排序算法，這些排序算法雖然都在線性時間，但是都是在對輸入數組有一定的約束的前提下才行。 這篇文章參看了《算法導論》第2、3、4、6、7、8章而總結。
算法的由來：9世紀波斯數學家提出的：“al-Khowarizmi”


排序的定義： 輸入：n個數：a1,a2,a3,...,an 輸出：n個數的排列:a1',a2',a3',...,an'，使得a1'<=a2'<=a3'<=...<=an'。
In-place sort（不占用額外內存或占用常數的內存）：插入排序、選擇排序、冒泡排序、堆排序、快速排序。 Out-place sort：歸并排序、計數排序、基數排序、桶排序。
當需要對大量數據進行排序時，In-place sort就顯示出優點，因為只需要占用常數的內存。 設想一下，如果要對10000個數據排序，如果使用了Out-place sort，則假設需要用200G的額外空間，則一臺老式電腦會吃不消，但是如果使用In-place sort，則不需要花費額外內存。
stable sort：插入排序、冒泡排序、歸并排序、計數排序、基數排序、桶排序。 unstable sort：選擇排序(5 8 5 2 9)、快速排序、堆排序。
為何排序的穩定性很重要？
在初學排序時會覺得穩定性有這么重要嗎？兩個一樣的元素的順序有這么重要嗎？其實很重要。在基數排序中顯得尤為突出，如下：



算法導論習題8.3-2說：如果對于不穩定的算法進行改進，使得那些不穩定的算法也穩定？ 其實很簡單，只需要在每個輸入元素加一個index，表示初始時的數組索引，當不穩定的算法排好序后，對于相同的元素對index排序即可。
基于比較的排序都是遵循“決策樹模型”，而在決策樹模型中，我們能證明給予比較的排序算法最壞情況下的運行時間為Ω(nlgn)，證明的思路是因為將n個序列構成的決策樹的葉子節點個數至少有n!，因此高度至少為nlgn。
線性時間排序雖然能夠理想情況下能在線性時間排序，但是每個排序都需要對輸入數組做一些假設，比如計數排序需要輸入數組數字范圍為[0,k]等。
在排序算法的正確性證明中介紹了”循環不變式“，他類似于數學歸納法，"初始"對應"n=1"，"保持"對應"假設n=k成立，當n=k+1時"。

一、插入排序

特點：stable sort、In-place sort 最優復雜度：當輸入數組就是排好序的時候，復雜度為O(n)，而快速排序在這種情況下會產生O(n^2)的復雜度。 最差復雜度：當輸入數組為倒序時，復雜度為O(n^2) 插入排序比較適合用于“少量元素的數組”。

其實插入排序的復雜度和逆序對的個數一樣，當數組倒序時，逆序對的個數為n(n-1)/2，因此插入排序復雜度為O(n^2)。 在算法導論2-4中有關于逆序對的介紹。
偽代碼：

證明算法正確性：
循環不變式：在每次循環開始前，A[1...i-1]包含了原來的A[1...i-1]的元素，并且已排序。
初始：i=2，A[1...1]已排序，成立。 保持：在迭代開始前，A[1...i-1]已排序，而循環體的目的是將A[i]插入A[1...i-1]中，使得A[1...i]排序，因此在下一輪迭代開 ? ? ? 始前，i++，因此現在A[1...i-1]排好序了，因此保持循環不變式。 終止：最后i=n+1，并且A[1...n]已排序，而A[1...n]就是整個數組，因此證畢。
而在算法導論2.3-6中還問是否能將偽代碼第6-8行用二分法實現？
實際上是不能的。因為第6-8行并不是單純的線性查找，而是還要移出一個空位讓A[i]插入，因此就算二分查找用O(lgn)查到了插入的位置，但是還是要用O(n)的時間移出一個空位。
問：快速排序（不使用隨機化）是否一定比插入排序快？
答：不一定，當輸入數組已經排好序時，插入排序需要O(n)時間，而快速排序需要O(n^2)時間。

遞歸版插入排序

二、冒泡排序

特點：stable sort、In-place sort 思想：通過兩兩交換，像水中的泡泡一樣，小的先冒出來，大的后冒出來。 最壞運行時間：O(n^2) 最佳運行時間：O(n^2)（當然，也可以進行改進使得最佳運行時間為O(n)）
算法導論思考題2-2中介紹了冒泡排序。
偽代碼：


證明算法正確性：
運用兩次循環不變式，先證明第4-6行的內循環，再證明外循環。
內循環不變式：在每次循環開始前，A[j]是A[j...n]中最小的元素。
初始：j=n，因此A[n]是A[n...n]的最小元素。 保持：當循環開始時，已知A[j]是A[j...n]的最小元素，將A[j]與A[j-1]比較，并將較小者放在j-1位置，因此能夠說明A[j-1]是A[j-1...n]的最小元素，因此循環不變式保持。 終止：j=i，已知A[i]是A[i...n]中最小的元素，證畢。
接下來證明外循環不變式：在每次循環之前，A[1...i-1]包含了A中最小的i-1個元素，且已排序：A[1]<=A[2]<=...<=A[i-1]。
初始：i=1，因此A[1..0]=空，因此成立。 保持：當循環開始時，已知A[1...i-1]是A中最小的i-1個元素，且A[1]<=A[2]<=...<=A[i-1]，根據內循環不變式，終止時A[i]是A[i...n]中最小的元素，因此A[1...i]包含了A中最小的i個元素，且A[1]<=A[2]<=...<=A[i-1]<=A[i] 終止：i=n+1，已知A[1...n]是A中最小的n個元素，且A[1]<=A[2]<=...<=A[n]，得證。
在算法導論思考題2-2中又問了”冒泡排序和插入排序哪個更快“呢？
一般的人回答：“差不多吧，因為漸近時間都是O(n^2)”。 但是事實上不是這樣的，插入排序的速度直接是逆序對的個數，而冒泡排序中執行“交換“的次數是逆序對的個數，因此冒泡排序執行的時間至少是逆序對的個數，因此插入排序的執行時間至少比冒泡排序快。

遞歸版冒泡排序



改進版冒泡排序

最佳運行時間：O(n) 最壞運行時間：O(n^2)

三、選擇排序

特性：In-place sort，unstable sort。 思想：每次找一個最小值。 最好情況時間：O(n^2)。 最壞情況時間：O(n^2)。
偽代碼：

證明算法正確性：
循環不變式：A[1...i-1]包含了A中最小的i-1個元素，且已排序。
初始：i=1，A[1...0]=空，因此成立。 保持：在某次迭代開始之前，保持循環不變式，即A[1...i-1]包含了A中最小的i-1個元素，且已排序，則進入循環體后，程序從 ? ? ? ? A[i...n]中找出最小值放在A[i]處，因此A[1...i]包含了A中最小的i個元素，且已排序，而i++，因此下一次循環之前，保持 ? ? ? 循環不變式：A[1..i-1]包含了A中最小的i-1個元素，且已排序。 終止：i=n，已知A[1...n-1]包含了A中最小的i-1個元素，且已排序，因此A[n]中的元素是最大的，因此A[1...n]已排序，證畢。

算法導論2.2-2中問了"為什么偽代碼中第3行只有循環n-1次而不是n次"？
在循環不變式證明中也提到了，如果A[1...n-1]已排序，且包含了A中最小的n-1個元素，則A[n]肯定是最大的，因此肯定是已排序的。

遞歸版選擇排序


遞歸式：
T(n)=T(n-1)+O(n)? => T(n)=O(n^2)

四、歸并排序

特點：stable sort、Out-place sort 思想：運用分治法思想解決排序問題。 最壞情況運行時間：O(nlgn) 最佳運行時間：O(nlgn)
分治法介紹：分治法就是將原問題分解為多個獨立的子問題，且這些子問題的形式和原問題相似，只是規模上減少了，求解完子問題后合并結果構成原問題的解。 分治法通常有3步：Divide（分解子問題的步驟） 、 Conquer（遞歸解決子問題的步驟）、 Combine（子問題解求出來后合并成原問題解的步驟）。 假設Divide需要f(n)時間，Conquer分解為b個子問題，且子問題大小為a，Combine需要g(n)時間，則遞歸式為： T(n)=bT(n/a)+f(n)+g(n)
算法導論思考題4-3（參數傳遞）能夠很好的考察對于分治法的理解。
就如歸并排序，Divide的步驟為m=(p+q)/2，因此為O(1)，Combine步驟為merge()函數，Conquer步驟為分解為2個子問題，子問題大小為n/2，因此： 歸并排序的遞歸式：T(n)=2T(n/2)+O(n)
而求解遞歸式的三種方法有： (1)替換法：主要用于驗證遞歸式的復雜度。 (2)遞歸樹：能夠大致估算遞歸式的復雜度，估算完后可以用替換法驗證。 (3)主定理：用于解一些常見的遞歸式。
偽代碼：


證明算法正確性：
其實我們只要證明merge()函數的正確性即可。 merge函數的主要步驟在第25~31行，可以看出是由一個循環構成。
循環不變式：每次循環之前，A[p...k-1]已排序，且L[i]和R[j]是L和R中剩下的元素中最小的兩個元素。 初始：k=p，A[p...p-1]為空，因此已排序，成立。 保持：在第k次迭代之前，A[p...k-1]已經排序，而因為L[i]和R[j]是L和R中剩下的元素中最小的兩個元素，因此只需要將L[i]和R[j]中最小的元素放到A[k]即可，在第k+1次迭代之前A[p...k]已排序，且L[i]和R[j]為剩下的最小的兩個元素。 終止：k=q+1，且A[p...q]已排序，這就是我們想要的，因此證畢。
歸并排序的例子：

問：歸并排序的缺點是什么？
答：他是Out-place sort，因此相比快排，需要很多額外的空間。
問：為什么歸并排序比快速排序慢？
答：雖然漸近復雜度一樣，但是歸并排序的系數比快排大。
問：對于歸并排序有什么改進？
答：就是在數組長度為k時，用插入排序，因為插入排序適合對小數組排序。在算法導論思考題2-1中介紹了。復雜度為O(nk+nlg(n/k)) ，當k=O(lgn)時，復雜度為O(nlgn)

五、快速排序

Tony Hoare爵士在1962年發明，被譽為“20世紀十大經典算法之一”。 算法導論中講解的快速排序的PARTITION是Lomuto提出的，是對Hoare的算法進行一些改變的，而算法導論7-1介紹了Hoare的快排。 特性：unstable sort、In-place sort。 最壞運行時間：當輸入數組已排序時，時間為O(n^2)，當然可以通過隨機化來改進（shuffle array 或者 randomized select pivot）,使得期望運行時間為O(nlgn)。 最佳運行時間：O(nlgn) 快速排序的思想也是分治法。 當輸入數組的所有元素都一樣時，不管是快速排序還是隨機化快速排序的復雜度都為O(n^2)，而在算法導論第三版的思考題7-2中通過改變Partition函數，從而改進復雜度為O(n)。
注意：只要partition的劃分比例是常數的，則快排的效率就是O(nlgn)，比如當partition的劃分比例為10000:1時（足夠不平衡了），快排的效率還是O(nlgn)
“A killer adversary for quicksort”這篇文章很有趣的介紹了怎么樣設計一個輸入數組，使得quicksort運行時間為O(n^2)。
偽代碼：


隨機化partition的實現：


改進當所有元素相同時的效率的Partition實現：


證明算法正確性：
對partition函數證明循環不變式：A[p...i]的所有元素小于等于pivot，A[i+1...j-1]的所有元素大于pivot。 初始：i=p-1,j=p，因此A[p...p-1]=空，A[p...p-1]=空，因此成立。 保持：當循環開始前，已知A[p...i]的所有元素小于等于pivot，A[i+1...j-1]的所有元素大于pivot，在循環體中， ????????? ? -?如果A[j]>pivot，那么不動，j++，此時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。 最優時間：O(nlgn) 最差時間：O(nlgn) 此篇文章介紹了堆排序的最優時間和最差時間的證明：http://blog.csdn.net/xiazdong/article/details/8193625? 思想：運用了最小堆、最大堆這個數據結構，而堆還能用于構建優先隊列。
優先隊列應用于進程間調度、任務調度等。 堆數據結構應用于Dijkstra、Prim算法。


證明算法正確性：
（1）證明build_max_heap的正確性： 循環不變式：每次循環開始前，A[i+1]、A[i+2]、...、A[n]分別為最大堆的根。
初始：i=floor(n/2)，則A[i+1]、...、A[n]都是葉子，因此成立。 保持：每次迭代開始前，已知A[i+1]、A[i+2]、...、A[n]分別為最大堆的根，在循環體中，因為A[i]的孩子的子樹都是最大堆，因此執行完MAX_HEAPIFY(A,i)后，A[i]也是最大堆的根，因此保持循環不變式。 終止：i=0，已知A[1]、...、A[n]都是最大堆的根，得到了A[1]是最大堆的根，因此證畢。
（2）證明heapsort的正確性： 循環不變式：每次迭代前，A[i+1]、...、A[n]包含了A中最大的n-i個元素，且A[i+1]<=A[i+2]<=...<=A[n]，且A[1]是堆中最大的。
初始：i=n，A[n+1]...A[n]為空，成立。 保持：每次迭代開始前，A[i+1]、...、A[n]包含了A中最大的n-i個元素，且A[i+1]<=A[i+2]<=...<=A[n]，循環體內將A[1]與A[i]交換，因為A[1]是堆中最大的，因此A[i]、...、A[n]包含了A中最大的n-i+1個元素且A[i]<=A[i+1]<=A[i+2]<=...<=A[n]，因此保持循環不變式。 終止：i=1，已知A[2]、...、A[n]包含了A中最大的n-1個元素，且A[2]<=A[3]<=...<=A[n]，因此A[1]<=A[2]<=A[3]<=...<=A[n]，證畢。

七、計數排序

特性：stable sort、out-place sort。 最壞情況運行時間：O(n+k) 最好情況運行時間：O(n+k)
當k=O(n)時，計數排序時間為O(n)
偽代碼：

八、基數排序

本文假定每位的排序是計數排序。 特性：stable sort、Out-place sort。 最壞情況運行時間：O((n+k)d) 最好情況運行時間：O((n+k)d)
當d為常數、k=O(n)時，效率為O(n) 我們也不一定要一位一位排序，我們可以多位多位排序，比如一共10位，我們可以先對低5位排序，再對高5位排序。 引理：假設n個b位數，將b位數分為多個單元，且每個單元為r位，那么基數排序的效率為O[(b/r)(n+2^r)]。 當b=O(nlgn)，r=lgn時，基數排序效率O(n)
比如算法導論習題8.3-4：說明如何在O(n)時間內，對0~n^2-1之間的n個整數排序？ 答案：將這些數化為2進制，位數為lg(n^2)=2lgn=O(lgn)，因此利用引理，b=O(lgn)，而我們設r=lgn，則基數排序可以在O(n)內排序。
基數排序的例子：



證明算法正確性：
通過循環不變式可證，證明略。

九、桶排序

假設輸入數組的元素都在[0,1)之間。 特性：out-place sort、stable sort。 最壞情況運行時間：當分布不均勻時，全部元素都分到一個桶中，則O(n^2)，當然[算法導論8.4-2]也可以將插入排序換成堆排序、快速排序等，這樣最壞情況就是O(nlgn)。 最好情況運行時間：O(n)
桶排序的例子：

偽代碼：


證明算法正確性：
對于任意A[i]<=A[j]，且A[i]落在B[a]，A[j]落在B[b]，我們可以看出a<=b，因此得證。

總結

以上是生活随笔為你收集整理的九大排序算法总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。