最近在學習算法，跟著<Algorithms>這本書，可能是自己水平不夠吧，看完排序算法后各種，希爾，歸并，快排，堆的實現在腦子里亂成一鍋粥，所以就打算大概總結一下，不求精確，全面，只想用平白的語言來理一理，如有錯誤之處，請直言。

　　為什么所有的算法書籍都重墨介紹排序，一、對一組數據進行排序在生活中是如此的常見，我們常常需要使用它；二、排序是實現很多一些高級算法的基礎，一些復雜問題，如果處理的是已經拍過序的數據，那么就容易處理很多；三、排序算法中包含了很多重要的思想和方法，對于其他算法的研究也具有借鑒意義。研究排序算法之前，有一些關于算法的基礎是需要掌握的。什么是好的算法？當然是算的快的算法，就是所謂的時間復雜性分析。計算機的內存是有限的，如果算法使用的空間也比較小，那就更好了，所謂的空間復雜度分析。如果代碼寫起來簡單又好理解，這簡直就是完美。此外針對不同的輸入，同一個算法的性能也有很大的區別，所以也可以分別討論。一些搞算法的人將這些情況總結起來，形成了科學的方法，甚至抽象成了思想。包括：算法的時間復雜度，該算法的運行時間？這個問題，我們能達到的最快運行時間；空間復雜度，算法解決問題使用多少空間。輸入模型，針對不容的輸入情況，比如大致排好序的，重復元素多的等等。算的又快，空間利用少，針對不同輸入保持穩定高效，這樣的算法是完美的算法。

　　排序-比如，給你一個包含N個隨機double元素的數組，想要得到一個按大小排好序的數組。

1，選擇排序/selection sort

　　選擇排序大概是最簡單易于理解的排序方法了，想象有一群高矮不同的人群，現在要將他們按高矮排一列。你可以從這群人中找出最矮的那個，放到最前面，然后找出第二矮的，依次下去直到排完。

1 public class Selection{ 2 private static boolean less(Comparable[] a,int i,int j){ 3 return a[i].compareTo(a[j])<0; 4 } 5 private static void exch(Comparable[] a,int i,int j){ 6 Comparable temp=a[i]; 7 a[i]=a[j]; 8 a[j]=temp; 9 } 10 public static void sort(Comparable[] a){ 11 int N=a.length; 12 for(int i=0;i<N-1;i++){ 13 int temp=i; 14 for(int j=i+1;j<N;j++) 15 if(less(a,j,temp)) temp=j; 16 exch(a,i,temp); 17 } 18 } 19 }

這里面有兩個函數：less(),exch(),前者以索引比較數組中的兩個元素的大小，后者以索引交換兩個元素的位置。之所以將兩個操作封裝成兩個函數，是為了算法分析的方便。以后所有的算法都只使用著兩個操作，分析也主要集中于不同算法執行的著兩個操作的次數,因為其他的操作都是常數次的，只有這兩個操作是與N有關的。

? ? 分析：對于選擇排序，我們可以看到，比較的次數為(N-1)+(N-2)+...1=N²/2，平方級別；交換的次數為N-1，線性級別。非常穩定，無論輸入如何，效率不變。

2.插入排序/Insertion sort

　　從數組左邊到右邊遍歷元素，如果元素i小于前一個元素，將i與i-1交換，重復這個操作直到i落到合適的位置。

1 public class Insertion{ 2 private static boolean less(Comparable[] a,int i,int j){ 3 return a[i].compareTo(a[j])<0; 4 } 5 private static void exch(Comparable[] a,int i,int j){ 6 Comparable temp=a[i]; 7 a[i]=a[j]; 8 a[j]=temp; 9 } 10 public static void sort(Comparable[] a){ 11 int N=a.length; 12 for(int i=1;i<N;i++) 13 while(i>0 && less(a,i,i-1)){ 14 exch(a,i,i-1); 15 i--; 16 } 17 } 18 }

分析：這個算法是依賴于輸入的，最好的情況是數組已經排好序，那么只需要經過N-1次比較，0次交換，就能完成。最壞的情況，數組是逆序的，那么需要1+2+...(N-1)=N²/2次比較，同樣多次的交換達成目標。平均情況下同樣分析可以知道，需要N²/4次比較和同樣多次交換達成目標。值得注意的一點是，插入排序對于基本有序的數組排序很有效果，因為只需要線性次數的比較和較少次操作，就能達成目標。

?

3.冒泡排序/bubble sort

　　對于很多沒學過算法的人，聽到這個名字感覺很高大上，但其實這是個很簡單的算法，效率也較低，基本上不怎么用。方法就是進行一個N次的循環，每次循環遍歷數組元素，將相鄰兩個元素中較大的放后面，因為元素像泡泡一樣浮出得名。有兩個優化策略，1、每次重復，遍歷數組長度-1，2、當一次遍歷沒有進行交換，表明已經排好序，跳出循環而不用執行固定的循環次數。

1 public class Bubble{ 2 private static boolean less(Comparable[] a,int i,int j){...代碼上同} 3 private static void exch(Comparable[] a,int i,int j){...代碼上同} 4 public static void sort(Comparable[] a){ 5 int N=a.length; 6 int temp=1; 7 for(int i=0;i<N-1 && temp==1;i++){ 8 temp=0; 9 for(int j=0;j<N-i-1;j++){ 10 if(less(a,j+1,j)){ 11 exch(a,j,j+1); 12 temp=1; 13 } 14 } 15 } 16 } 17 }

分析：冒泡排序感覺跟插入排序有很多相同，也是依賴于輸入的，最好的情況:順序排列的數組，需要N-1次比較和0次交換，達成目標。最差的情況：逆序排列：需要1+2+...(N-1)=N²/2次比較，同樣多次的交換達成目標。

　　以上是三種最基本的排序方式，可以看到三者一般情況下都是平方級別的，所以相互之間的速度差別為常數級別的，試驗發現，插入排序相當是較快的一種，但快的有限，大概比選擇排序快0.7倍。

　　實際上通過分析可以發現，三種排序方法效率都有某種程度的浪費，所以可以對其進行優化，比如一種對插入排序的優化，希爾排序。

?

4.希爾排序/shell short

　　希爾排序有點難理解，通過觀察插入排序，我們發現它的一個性能問題是每次只能將一個元素和相鄰位置的交換，比如將一個最小的元素從尾端移動到頭端，那么就需要N-1次移動，有沒有辦法一次移動多步呢，我們可以通過增加步長來實現。

　　希爾排序的特點是先構造一個遞增序列，比如下面代碼中所用的（1，4，13，40，121...）序列。先構造一個h有序的數組，比如h=13，即i-h,i,i+h,i+2h，等在數組內是有序的，然后縮小h的范圍令h=4，在構造一個h有序的數組。直到h=1，那么最終得到一個h=1有序的數組，即為目標數組。

　　遞增序列的選擇多種多樣，這里選擇h=3*h+1，只是因為比較好構造，性能尚可，也可以不用構造直接把遞增序列放到一個數組中。遞增序列的選擇對于算法效率有很大的影響，如何根據輸入找到最佳的遞增序列，以實現最佳效率是個非常復雜的問題。

1 public class Shell{ 2 private static boolean less(Comparable[] a,int i,int j){代碼同上} 3 private static void exch(Comparable[] a,int i,int j){代碼同上} 4 public static void sort(Comparable[] a){ 5 int N=a.length; 6 int h=1; 7 while(3*h<N) h=3*h+1; 8 while(h>0){ 9 for(int i=h;i<N;i++){ 10 while(i>=h && less(a,i,i-h)){ 11 exch(a,i,i-h); 12 i-=h; 13 } 14 } 15 h=h/3; 16 } 17 } 18 }

分析：希爾排序的性能很難分析，因為至今還沒有確定的最佳遞增序列，但是它的性能大于插入排序和選擇排序是確定的，數據量越到優勢越明顯，經過試驗，希爾排序的時間是小于平方級別的，大概在N^3/4級別。對于一個10萬隨機數據的數組，希爾排序大概比插入排序快600倍。

　　

　　從上面的分析可以看出，希爾排序已經比三種基本排序快了不少，對于一般長度的數組，希爾排序已經夠用了，但還有沒有更快的算法呢？排序算法的速度極限在哪里？下面介紹兩種算法：鼎鼎大名的-----歸并排序和被稱為20世紀最牛逼算法之一的----快速排序，以及他們所體現的分治思想。

5.歸并排序/merge sort

　　想象一下，比如我們有兩個有序的數組，[2,2,5,9,22,88]和[6,9,11,13,19,38]，如果我們想把二者合并為一個數組該怎么做，我們可以創建一個長度為兩者之和的新數組，分別用索引i，j代表二者中最小元素的索引，每次比較兩個元素的大小，將較小的元素放入新數組，其索引加1。直到到達數組尾部。代碼如下：?

?

1 public class Merge{ 2 public static int[] merge(int[] a,int [] b){ 3 int M=a.length,N=b.length; 4 int[] array=new int[M+N]; 5 int i=0,j=0,k=0; 6 for(int h=0;h<M+N;h++){ 7 if(i>=M) array[k++]=b[j++]; 8 else if(j>=N) array[k++]=a[i++]; 9 else if(a[i]<=b[j]) array[k++]=a[i++]; 10 else array[k++]=b[j++]; 11 } 12 return array; 13 } 14 }

?

這段代碼接收兩個數組作為參數，返回一個新的合并后的數組，這就叫做歸并操作。歸并算法就是將一個數組先分成兩個數組，對兩個數組歸并，再對分成的兩個數組，切分，歸并。總的來看，歸并是一種遞歸切分數組，然后依次歸并的操作。代碼如下：

?

1 public class Merge{ 2 private static Comparable[] aux;//聲明一個輔助數組aux 3 private static boolean less(Comparable[] a,int i,int j){代碼同上} 4 private static void exch(Comparable[] a,int i,int j){代碼同上} 5 //歸并操作部分 6 private static void merge(Comparable[] a,int lo,int mid,int hi){ 7 int i=lo,j=mid+1; 8 for(int k=lo;k<=hi;k++) 9 aux[k]=a[k];//將待歸并數組復制到輔助數組中 10 for(int k=lo;k<=hi;k++){ 11 if(i>mid) a[k]=aux[j++]; 12 else if(j>hi) a[k]=aux[i++]; 13 else if(less(aux,j,i)) a[k]=aux[j++]; 14 else a[k]=aux[i++]; 15 } 16 } 17 public static void sort(Comparable[] a){ 18 int N=a.length; 19 aux=new Comparable[N]; 20 sort(a,0,N-1); 21 } 22 //二分切分數組，遞歸調用 23 private static void sort(Comparable[] a,int lo,int hi){ 24 if(lo>=hi) return; 25 int mid=lo+(hi-lo)/2; 26 sort(a,lo,mid); 27 sort(a,mid+1,hi); 28 merge(a,lo,mid,hi); 29 } 30 }

　　這段遞歸算法代碼寫的頭都大了，結果bug無數，改了N久。思想還是很好理解的，就是遞歸的切分數組，每次切分后對切分出的數組做歸并操作。經過牛人分析得知，將數組每次平分時效率最高的。

時間分析，歸并算法的時間分析是比較復雜的，這里我們引入一個決策樹的模型，歸并算法適用于該模型的一種情況，對應于一個公式。不了解的話可以參看網易公開課里MIT開設的<算法導論>課程第三講，我只能大概聽懂，根本講不出來。T(N)=2T(N/2)+Θ(n)，其中Θ(n)反映的是歸并操作與N的關系，這里是線性的，套用公式得到T(N)=Θ(Nlgⁿ)，所以歸并算法的時間是線性對數級的，當N足夠大時，該算法是遠遠優于上面四種算法的。

　　另外需要注意的一點是該算法過程中的空間占用，需要構造一個與a等大的數組；這個算法也是可以優化的，比如在數組較小時，遞歸調用函數占用了大量的成本，可以在切分出的數組較小時，使用插入排序。

?

　　對于排序算法來說，算法最快能有多快，線性對數級別的最快的嗎？可以使用上面提到的決策數模型來進行分析，對于N個數的數組，將其排序可以有N!種情況，對于數組的排序，我們可以把它分解成一個決策樹模型，樹的高度是h,葉子結點的數量最多為2^h,所以2^h?>=N!,根據斯特靈公式，h=NlgN，所以得出一個結論，那就是對于一般的N個元素的隨機數組，基于比較操作與交換操作的排序的算法最快也只能達到線性對數級別。上面的歸并排序就是這樣一種算法，所以，歸并是漸近最優的。

?

　　歸并排序就是終點嗎？不，還有吊炸天的快速排序呢，歸并排序雖然時間性能上接近最優，但需要輔助數組，當要排序數組非常大時，這一點會成為它的缺陷。下面介紹一種更優同樣基于分治思想的算法--快速排序。

?

?

6.快速排序/quick sort

　　我們想象這樣一種情況，有一個數組[9,7,18,3,17,25]，我想把所有小于9的元素都放在9的前面，大于9的元素都放在9后面，返回9在數組中的位置。該如何實現？代碼如下：

1 public static int merge(int[] a){ 2 int num=a[0]; 3 int i=1,j=a.length-1; 4 //從前往后找比num大的元素，從后往前找比num小的元素，二者交換，指針相遇時跳出循環 5 while(true){ 6 while(a[i]<num) i++; 7 while(a[j]>num) j--; 8 if(i>=j) break; 9 int temp=a[i]; 10 a[i]=a[j]; 11 a[j]=temp; 12 } 13 //將該元素放到合適的位置上 14 int temp=a[j]; 15 a[j]=a[0]; 16 a[0]=temp; 17 return j; 18 }

?

其實對于數組中任何一個元素，我們都可以以這個元素來實現對該數組的切分，只需要將num=a[i]，i為你想要切分元素的索引。基于這種數組元素的切分方法，我們來實現快速排序。代碼如下：

?

1 public class Quick{ 2 private static boolean less(Comparable[] a,int i,int j){代碼同上} 3 private static void exch(Comparable[] a,int i,int j){代碼同上} 4 //以數組第一個元素切分數組 5 private static int partition(Comparable[] a,int lo,int hi){ 6 int i=lo,j=hi+1; 7 while(true){ 8 while(less(a,++i,lo)) if(i==hi) break; 9 while(less(a,lo,--j)) if(j==lo) break; 10 if(i>=j) break; 11 exch(a,i,j); 12 } 13 exch(a,lo,j); 14 return j; 15 } 16 //遞歸調用私有sort方法 17 private static void sort(Comparable[] a,int lo,int hi){ 18 if(lo>=hi) return; 19 int j=partition(a,lo,hi); 20 sort(a,lo,j-1); 21 sort(a,j+1,hi); 22 } 23 //quick sort的對外接口 24 public static void sort(Comparable[] a){ 25 StdRandom.shuffle(a);//將數組變為亂序 26 sort(a,0,a.length-1); 27 } 28 }

需要注意的一點是在sort方法里，首先調用了StdRandom.shuffle()方法，來將數組變為亂序。shuffle()的實現也較為簡單，遍歷數組，將當前元素與后面一堆元素中的一個隨機元素交換位置。注意，是當前元素后面的隨機元素。這樣做是為了使快排能適應更多不同的輸入，比如輸入數組第一個值正好是數組的最大值和最小值，以后每次第一個元素都是該切分數組的最大或最小值，那么快排的效率會變得非常糟糕。將數組排為亂序，可以確保這種極端情況不會出現。當然也可以采用另外一種方法，就是在每次切分數組時，選擇數組中的隨機元素作為切分值，這也可以避免極端情況的出現。

　　分析：快速排序和歸并一樣，經過數學證明，其時間級別是線性對數級別的。約為1.39倍NlgN，而且該算法不需要額外的空間需求，幾乎是一般情況下最優秀的算法。所以得到了廣泛的應用。?

　　快速排序也是可以改進的，以實現更高的效率，因為快排是基于函數的遞歸調用，所以當對較小的子數組排序時，可以切換到插入排序。對于重復值較多的數組，可以使用三向切分等。

?

7.堆排序/heap sort

　　堆排序是基于二叉堆實現的排序方法。二叉堆就是一個從索引1到N的有一定順序的數組。數組中的索引為k的元素一定大于等于索引為2*k，2*k+1的元素，用二叉堆得樹結構的話，就是說父節點一定大于等于（小于等于）任一個子節點。由此可知，其根節點，即索引為1的元素為數組元素中的最大值。

二叉堆數據結構的實現基于數組和三個特殊的操作數組中元素的方法。

　　1.往二叉堆中添加元素，構造新的二叉堆：將該元素添加到隊列尾部，上浮該元素到合適的位置。

　　2.刪除堆中的最大元素，備份索引為1的元素，將索引為1的元素和隊尾元素互換，下沉索引為1的元素到合適位置，隊列尾元素清空，更新隊列長，返回備份元素。

　　3.根據二叉堆的性質實現元素的下沉和上浮操作。

根據以上內容可以判斷出二叉堆得實現主要是在數組中利用上浮和下沉來構造堆有序的數組，數組索引從1到N存儲元素。

1 //假設我們現在有一個長為N+1的數組 2 //將數組中索引為k的元素上浮到合適位置 3 public static void swim(int k){ 4 while(k>1 && a[k]>a[k/2]){ 5 exch(a,k,k/2); 6 k/=2; 7 } 8 } 9 10 //將數組中索引為k的元素下沉到合適的位置 11 public static void sink(int k){ 12 while(2*k <=N){ 13 int j=2*k; 14 if(j<N && a[j]<a[j+1]) j++; //確定j為k的較大的那個子節點 15 if(a[k]>=a[j]) break; //如果元素大于兩個子節點，說明落到了合適位置 16 exch(a,k,j); //否則下沉該元素到合適位置 17 k=j; //更新k的值，繼續循環 18 } 19 }

根據上面的兩個基礎操作，就能實現優先隊列中最重要的刪除最大元素和插入新元素的操作。

?

下面我們根據這個思想來看看堆排序。

　　一，對于一個無序數組，先從左到右遍歷數組，上浮每個元素，使得數組變為堆有序；如果改為從右到左，下沉每個元素，會更高效（可以從N/2到1下沉，單個葉子節點無法下沉，不考慮）。

　　二，指針從數組尾開始遞減，持續交換數組的根節點元素和尾元素，下沉交換后的尾元素，這里改寫了下沉函數，將已交換的元素不考慮。最后得到一個有序數組。

這里需要注意兩點：1，堆的實現是從1到N的，而我們傳入的數組是從0到N-1的，所以在訪問數組元素時（比較和交換）將索引減一即可。2，也可以將數組按從大到小排序，只需要改變比較規則>和<，即可。

代碼如下：

1 import java.util.Arrays; 2 public class Test{ 3 public static void heapSort(int[] a){ 4 //將數組建立堆序 5 int N=a.length; 6 for(int k=N/2;k>=1;k--){ 7 sink(a,k,N); 8 } 9 //依次取出最大值，將數組排序 10 while(N>1){ 11 exch(a,N--,1); 12 sink(a,1,N); 13 } 14 } 15 16 //下沉函數 17 private static void sink(int[] a,int k,int N){ 18 while(2*k <=N){ 19 int j=2*k; 20 if(j<N && less(a,j,j+1)) j++; //j為較大的子節點 21 if(! less(a,k,j)) break; 22 exch(a,k,j); 23 k=j; 24 } 25 } 26 27 //交換數組中元素 28 private static void exch(int[] a,int i,int j){ 29 i--;j--; //基于堆索引的特殊性，將參數減一 30 int temp=a[i]; 31 a[i]=a[j]; 32 a[j]=temp; 33 } 34 35 //比較數組中元素 36 private static boolean less(int[] a,int i,int j){ 37 i--;j--; //基于堆索引的特殊性，將參數減一 38 return a[i]<a[j] ? true :false; 39 } 40 41 //測試排序方法 42 public static void main(String[] args){ 43 int[] a={5,4,2,1,7,0,3,6}; 44 heapSort(a); 45 System.out.println(Arrays.toString(a)); 46 } 47 } View Code

?堆排序算法也是線性對數級別的算法，對于任何為N的數組，排序都可以在2NlgN時間內完成，但排序算法很少使用它的原因是它無法利用緩存，數組元素很少和相鄰元素比較。而相比較下，快排，歸并，希爾等排序算法對緩存的利用要高的多。

二叉堆這種數據結構更多的應用在基于優先隊列的一些需求上。

?

　　

轉載于:https://www.cnblogs.com/charsandrew/p/5918514.html

總結

以上是生活随笔為你收集整理的搞不懂的算法-排序篇1的全部內容，希望文章能夠幫你解決所遇到的問題。

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