版權信息 原文鏈接：[常用排序算法總結（性能+代碼）](https://segmentfault.com/a/1190000002595152) --- 雖是讀書筆記，但是如轉載請注明出處[http://segmentfault.com/blog/exploring/](http://segmentfault.com/blog/exploring/) ..拒絕伸手復制黨 想更一進步的支持我，請掃描下方的二維碼，你懂的~ ##  ## 1\. 插入排序 ### 1.1 性能分析 時間復雜度`O(n^2)`, 空間復雜度`O(1)` 排序時間與輸入有關：輸入的元素個數；元素已排序的程度。 最佳情況，輸入數組是已經排好序的數組，運行時間是`n`的線性函數； 最壞情況，輸入數組是逆序，運行時間是`n`的二次函數。 ### 1.2 核心代碼 ~~~ public void sort(){ int temp; for(int i = 1; i<arraytoSort.length; i++){ for(int j = i-1; j>=0; j--){ if( arraytoSort[j+1] < arraytoSort[j] ){ temp = arraytoSort[j+1]; arraytoSort[j+1] = arraytoSort[j]; arraytoSort[j] = temp; } } } } ~~~ ## 2.選擇排序 ### 2.1 性能分析 時間復雜度`O(n^2)`, 空間復雜度`O(1)` 排序時間與輸入無關，最佳情況，最壞情況都是如此, 不穩定 如?`{5,5,2}`。 ### 2.2核心代碼 ~~~ public void sort(){ for(int i = 0; i<arraytoSort.length-1; i++){ int min = i; int temp; //find min for(int j = i+1; j<arraytoSort.length ;j++){ if(arraytoSort[j] <arraytoSort[min]){ min = j; } } //swap the min with the ith element temp = arraytoSort[min]; arraytoSort[min] = arraytoSort[i]; arraytoSort[i] = temp; } } ~~~ ## 3\. 歸并排序 ### 3.1 性能分析 時間復雜度?`O(nlogn)`, 空間復雜度`O(n) +O(logn)` 排序時間與輸入無關，最佳情況，最壞情況都是如此, 穩定。 原理： 可以將數組分成二組。依次類推，當分出來的小組只有一個數據時，可以認為這個小組組內已經達到了有序，然后再合并相鄰的二個小組就可以了。這樣通過先遞歸的分解數列，再合并數列就完成了歸并排序 歸并排序的時間復雜度，合并耗費`O(n)`時間，而由完全二叉樹的深度可知，整個歸并排序需要進行`log_2n`次，因此，總的時間復雜度為?`O(nlogn)`，而且這是歸并排序算法中最好、最壞、平均的時間性能。 由于歸并排序在歸并過程中需要與原始記錄序列同樣數量的存儲空間存放歸并結果 以及 遞歸時深度為?`log_2n`?的棧空間，因此空間復雜度為`O(n+logn)`。 另外，對代碼進行仔細研究，發現 Merge 函數中有`if (L[i]<R[j])`?語句，這就說明它需要兩兩比較，不存在跳躍，因此歸并排序是一種穩定的排序算法。 也就是說，歸并排序是一種比較占用內存，但卻效率高且穩定的算法。 ### 3.2 核心代碼 ~~~ public int merge( int p, int q, int r ){ int count = 0; int[] right = assignlist(p,q); //賦值左半部分數組（賦值就是用for循環，還有一個哨兵：最后一個元素設置為maxvalue） int[] left = assignlist(q+1,r); //賦值有半部分數組 int i = 0; int j = 0; for(int k = p; k<=r; k++){ if(right[i] <= left[j]){ arraytoSort[k] = right[i]; i++; } else if(right[i] > left[j]){ arraytoSort[k] = left[j]; j++; count = count + (q - p + 1) -i; } } return count; } void MergeSort(int arry[],int start,int end) { if(start<end) { int mid=(start+end)/2;//數組重點 MergeSort(arry,start,mid);//遞歸調用，排序前半段arry[start...mid] MergeSort(arry,mid+1,end);//遞歸調用，排序后半段arry[mid+1,end] MergeArry(arry,start,mid,end);//歸并上述兩段有序數組。 } } ~~~ ### 3.3 延伸 求逆序對 ## 4冒泡排序 ### 4.1 性能分析 時間復雜度`O(n^2)`, 空間復雜度`O(1)`， 穩定，因為存在兩兩比較，不存在跳躍。 排序時間與輸入無關，最好，最差，平均都是`O(n^2)` ### 4.2 核心代碼 ~~~ for(int i=0;i<arraytoSort.length-1;i++){ for(int j=arraytoSort.length-1;j>=i+1;j--){ int temp; if(arraytoSort[j]<arraytoSort[j-1]) { temp = arraytoSort[j]; arraytoSort[j] = arraytoSort[j-1]; arraytoSort[j-1] = temp; } } } ~~~ ### 4.3 延伸 冒泡排序缺陷： 1. 在排序過程中，執行完當前的第i趟排序后，可能數據已全部排序完備，但是程序無法判斷是否完成排序，會繼續執行剩下的`(n-1-i)`趟排序。解決方法： 設置一個`flag`位, 如果一趟無元素交換，則?`flag = 0`; 以后再也不進入第二層循環。 2. 當排序的數據比較多時排序的時間會明顯延長，因為會比較?`n*(n-1)/2`次。 ## 5\. 堆排序 ### 5.1 性能分析 時間復雜度?`O(nlogn)`, 空間復雜度`O(1)`. 從這一點就可以看出，堆排序在時間上類似歸并，但是它又是一種原地排序，時間復雜度小于歸并的`O(n+logn)` 排序時間與輸入無關，最好，最差，平均都是`O(nlogn)`. 不穩定 堆排序借助了堆這個數據結構，堆類似二叉樹，又具有堆積的性質（子節點的關鍵值總小于（大于）父節點） 堆排序包括兩個主要操作: 1. 保持堆的性質heapify(A,i) 時間復雜度`O(logn)` 2. 建堆 buildmaxheap(A) 時間復雜度`O(n)`線性時間建堆 **對于大數據的處理**： 如果對100億條數據選擇Topk數據，選擇快速排序好還是堆排序好？ 答案是只能用堆排序。 堆排序只需要維護一個k大小的空間，即在內存開辟k大小的空間。而快速排序需要開辟能存儲100億條數據的空間，which is impossible. ### 5.2 核心代碼 ~~~ public class HeapSort { public void buildheap(int array[]){ int length = array.length; int heapsize = length; int nonleaf = length / 2 - 1; for(int i = nonleaf; i>=0;i--){ heapify(array,i,heapsize); } } public void heapify(int array[], int i,int heapsize){ int smallest = i; int left = 2*i+1; int right = 2*i+2; if(left<heapsize){ if(array[i]>array[left]){ smallest = left; } else smallest = i; } if(right<heapsize){ if(array[smallest]>array[right]){ smallest = right; } } if(smallest != i){ int temp; temp = array[i]; array[i] = array[smallest]; array[smallest] = temp; heapify(array,smallest,heapsize); } } public void heapsort(int array[]){ int heapsize = array.length; buildheap(array); for(int i=0;i<array.length-1;i++){ // swap the first and the last int temp; temp = array[0]; array[0] = array[heapsize-1]; array[heapsize-1] = temp; // heapify the array heapsize = heapsize - 1; heapify(array,0,heapsize); } } ~~~ ### 5.3 延伸 堆這種數據結構的很好的應用是 優先級隊列，如作業調度。 ## 6 快速排序 ### 6.1 性能分析 時間復雜度?`O(nlogn)`?空間復雜度`O（logn）`?不穩定 【兩個時間復雜度`O(nlogn)`?的排序算法都不穩定】 時間復雜度： 最壞`O（n^2）`?當**劃分不均勻**時候 逆序and排好序都是最壞情況 最好`O（n）`?當劃分均勻 `partition`的時間復雜度:?`O（n）`一共需要`logn`次`partition` 空間復雜度：遞歸造成的棧空間的使用，最好情況，遞歸樹的深度`logn`?空間復雜的`logn`，最壞情況，需要進行`n‐1`?遞歸調用，其空間復雜度為?`O(n)`，平均情況，空間復雜度也為`O(log2n)`。 由于關鍵字的比較和交換是跳躍進行的，因此，快速排序是一種不穩定的排序方法。 快速排序的每一輪就是將這一輪的基準數歸位，直到所有的數都歸為為止，排序結束。（類似冒泡）. partition是返回一個基準值的index, index 左邊都小于該index的數，右邊都大于該index的數。 快速排序之所比較快，因為相比冒泡排序，每次交換是跳躍式的。每次排序的時候設置一個基準點，將小于等于基準點的數全部放到基準點的左邊，將大于等于基準點的數全部放到基準點的右邊。這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數之間進行交換，交換的距離就大的多了。因此總的比較和交換次數就少了，速度自然就提高了。當然在最壞的情況下，仍可能是相鄰的兩個數進行了交換。因此快速排序的最差時間復雜度和冒泡排序是一樣的都是?`O(n^2)`，它的平均時間復雜度為?`O(nlogn)`。其實快速排序是基于 “二分” 的思想。 ### 6.2 核心代碼 ~~~ public class Quicksort { public int partition(int A[], int begin, int end){ int i = begin; int j = end; int q; int pivot = begin; int pivotnumber = A[pivot]; while(i!=j){ int temp; while(A[j]>pivotnumber && i<j){ j--; } while(A[i]<=pivotnumber && i<j) { i++; } temp = A[i]; A[i] = A[j]; A[j] = temp; } if(i == j){ int temp; temp =A[pivot]; A[pivot] = A[i]; A[i] = temp; } return i; } public void sort(int A[], int begin,int end){ if(begin<end){ int q; q = partition(A,begin, end); sort(A,begin, q-1); sort(A,q+1,end); } } public static void main(String[] args) { int array[] = {8,7,1,6,5,4,3,2}; Quicksort s = new Quicksort(); s.sort(array, 0, 7); for(int i=0;i<array.length;i++){ System. out.println("output " + array[i]); } } } ~~~ **非比較排序**： ，計數排序，基數排序，桶排序，時間復雜度能夠達到`O(n)`. 這些排序為了達到不比較的目的，對數據做了一些基本假設（限制）。如計數排序假設數據都`[0,n]`?范圍內，且范圍較小；基數排序假設數據都`[0,n]`?范圍內；也是桶排序假設數據均勻獨立的分布。 而且，非比較排序的空間要求比較高，用空間換取時間吧。當我們的待排序數組具備一些基數排序與桶排序要求的特性，且空間上又比較富裕時，桶排序與基數排序不失為最佳選擇。 ## 7\. 計數排序 我們希望能線性的時間復雜度排序，如果一個一個比較，顯然是不實際的，書上也在決策樹模型中論證了，比較排序的情況為`nlogn`的復雜度。既然不能一個一個比較，我們想到一個辦法，就是如果**在排序的時候就知道他的位置，那不就是掃描一遍，把他放入他應該的位置**不就可以了。 要知道**他的位置，我們只需要知道有多少不大于他不就可以了**嗎？ ### 7.1 性能分析 最好，最壞，平均的時間復雜度`O(n+k)`, 天了嚕， 線性時間完成排序，且穩定。 優點：不需要比較函數，利用地址偏移，對范圍固定在[0,k]的整數排序的最佳選擇。是排序字節串最快的排序算法。 缺點：由于用來計數的數組的長度取決于待排序數組中數據的范圍（等于待排序數組的最大值與最小值的差加上1），這使得計數排序對于數據范圍很大的數組，需要大量時間和內存。 ### 7.2 核心代碼 ~~~ public int[] countsort(int A[]){ int[] B = new int[A.length]; //to store result after sorting int k = max(A); int [] C = new int[k+1]; // to store temp for(int i=0;i<A.length;i++){ C[A[i]] = C[A[i]] + 1; } // 小于等于A[i]的數的有多少個, 存入數組C for(int i=1;i<C.length;i++){ C[i] = C[i] + C[i-1]; } //逆序輸出確保穩定-相同元素相對順序不變 for(int i=A.length-1;i>=0;i--){ B[C[A[i]]-1] = A[i]; C[A[i]] = C[A[i]]-1; } return B; } ~~~ ### 7.3 擴展 請給出一個算法，使之對給定的介于?`0`到?`k`?之間的?`n`個整數進行預處理，并能在`O(1)`?時間內回答出輸入的整數中有多少個落在?`[a...b]`?區間內。你給出的算法的預處理時間為`O(n+k)`。 分析：就是用計數排序中的預處理方法，獲得數組?`C[0...k`]，使得`C[i]`為不大于?`i`的元素的個數。這樣落入?`[a...b]`?區間內的元素個數有?`C[b]-C[a-1]`。 計數排序的重要性質是他是**穩定**的。一般而言，僅當衛星數據隨著被排序的元素一起移動時，穩定性才顯得比較重要。而這也是計數排序作為基數排序的子過程的重要原因 ## 8 基數排序 為什么要用基數排序 ？ 計數排序和桶排序都只是在研究一個關鍵字的排序，現在我們來討論有多個關鍵字的排序問題。 假設我們有一些二元組`(a,b)`，要對它們進行以`a`?為首要關鍵字，`b`的次要關鍵字的排序。我們可以先把它們先按照首要關鍵字排序，分成首要關鍵字相同的若干堆。然后，在按照次要關鍵值分別對每一堆進行單獨排序。最后再把這些堆串連到一起，使首要關鍵字較小的一堆排在上面。按這種方式的基數排序稱為?**MSD(Most Significant Dight) 排序**。 第二種方式是從最低有效關鍵字開始排序，稱為?**LSD(Least Significant Dight)排序**?。首先對所有的數據按照次要關鍵字排序，然后對所有的數據按照首要關鍵字排序。要注意的是，使用的排序算法必須是穩定的，否則就會取消前一次排序的結果。由于不需要分堆對每堆單獨排序，LSD 方法往往比 MSD 簡單而開銷小。下文介紹的方法全部是基于 LSD 的。 通常，基數排序要用到計數排序或者桶排序。使用計數排序時，需要的是Order數組。使用桶排序時，可以用鏈表的方法直接求出排序后的順序。  ### 8.1 性能分析 時間復雜度`O（n）`?(實際上是`O(d(n+k))`?d是位數) ### 8.2 核心代碼 ~~~ RADIX-SORT(A,d) for i = 1 to d do use a stable sort to sort array A on digit i ~~~ ### 8.3擴展 問題：對`[0,n^2-1]`的`n`?個整數進行線性時間排序。 思路 ： 把整數轉換為n進制再排序，每個數有兩位，每位的取值范圍是`[0..n-1]`，再進行基數排序 [http://blog.csdn.net/mishifangxiangdefeng/article/details/7685839](http://blog.csdn.net/mishifangxiangdefeng/article/details/7685839) 問題： 給定一個字符串數組，其中不同的串包含的字符數可能不同，但所有串中總的字符個數為 n。說明如何在 O(n) 時間內對該數組進行排序 ## 9\. 桶排序 桶排序的思想近乎徹底的分治思想。 桶排序假設待排序的一組數**均勻獨立**的分布在一個范圍中，并將這一范圍劃分成幾個子范圍（桶）。 然后基于某種映射函數`f`?，將待排序列的關鍵字?`k`?映射到第`i`個桶中 (即桶數組`B`?的下標`i`) ，那么該關鍵字`k`?就作為?`B[i]`中的元素 (每個桶`B[i]`都是一組大小為`N/M`?的序列 )。 接著將各個桶中的數據有序的合并起來 : 對每個桶`B[i]`?中的所有元素進行比較排序 (可以使用快排)。然后依次枚舉輸出?`B[0]....B[M]`?中的全部內容即是一個有序序列。 補充： 映射函數一般是?`f = array[i] / k`;?`k^2 = n`;?`n`是所有元素個數  ### 9.1 性能分析 平均時間復雜度為線性的?`O(n+C)`?最優情形下，桶排序的時間復雜度為`O(n)`。 桶排序的空間復雜度通常是比較高的，額外開銷為`O(n+m)`（因為要維護 M 個數組的引用）。 就是桶越多，時間效率就越高，而桶越多，空間卻就越大，由此可見時間和空間是一個矛盾的兩個方面。 算法穩定性 : 桶排序的穩定性依賴于桶內排序。如果我們使用了快排，顯然，算法是不穩定的。 [一個講bucket排序非常好的文章](http://hxraid.iteye.com/blog/647759) 桶排序利用函數的映射關系，減少了幾乎所有的比較工作。實際上，桶排序的 f(k) 值的計算，其作用就相當于快排中劃分，已經把大量數據分割成了基本有序的數據塊 (桶)。然后只需要對桶中的少量數據做先進的比較排序即可。 對 N 個關鍵字進行桶排序的時間復雜度分為兩個部分： (1) 循環計算每個關鍵字的桶映射函數，這個時間復雜度是?`O(n)`。 (2) 利用先進的比較排序算法對每個桶內的所有數據進行排序，其時間復雜度為?`∑ O(ni*logni)`?。其中?`ni`?為第?`i`個桶的數據量。 很顯然，第 (2) 部分是桶排序性能好壞的決定因素。這就是一個時間代價和空間代價的權衡問題了。 ### 9.2 核心代碼 ### 9.3擴展 ##  ## in summary  關于穩定性： * 選擇排序、快速排序、希爾排序、堆排序不是穩定的排序算法， * 冒泡排序、插入排序、歸并排序和基數排序是穩定的排序算法。 * 常用時間復雜度的大小關系：`O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)`