九大排序算法再總結

2019-11-06 06:37:36

字體：大中小

來源：轉載

供稿：網友

本文是 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%20sort、stable%20sort。最壞情況運行時間：當分布不均勻時，全部元素都分到一個桶中，則O(n^2)，當然[算法導論8.4-2]也可以將插入排序換成堆排序、快速排序等，這樣最壞情況就是O(nlgn)。最好情況運行時間：O(n)桶排序的例子：偽代碼：證明算法正確性：對于任意A[i]<=A[j]，且A[i]落在B[a]，A[j]落在B[b]，我們可以看出a<=b，因此得證。原文地址 http://blog.csdn.net/xiazdong/article/details/8462393

上一篇：對個geek青年的狀態機，查表純C實現的代碼修改

下一篇：【面試題】劍指offer14