摘要：是排序字節串最快的排序算法。計數排序的重要性質是他是穩定的。要注意的是，使用的排序算法必須是穩定的，否則就會取消前一次排序的結果。通常，基數排序要用到計數排序或者桶排序。

雖是讀書筆記，但是如轉載請注明出處http://segmentfault.com/blog/exploring/
..拒絕伸手復制黨

想更一進步的支持我，請掃描下方的二維碼，你懂的~

時間復雜度O(n^2), 空間復雜度O(1)
排序時間與輸入有關：輸入的元素個數；元素已排序的程度。
最佳情況，輸入數組是已經排好序的數組，運行時間是n的線性函數； 最壞情況，輸入數組是逆序，運行時間是n的二次函數。

java  public void sort(){
        int temp;
        for(int i = 1; i=0; j--){
                if( arraytoSort[j+1] < arraytoSort[j] ){
                    temp = arraytoSort[j+1];
                    arraytoSort[j+1] = arraytoSort[j];
                    arraytoSort[j] = temp;
                }   
            }   
        }
    }

java public void sort(){ 
        for(int i = 0; i

3. 歸并排序

3.1 性能分析

時間復雜度 O(nlogn), 空間復雜度O(n) +O(logn)

排序時間與輸入無關，最佳情況，最壞情況都是如此, 穩定。

原理：

可以將數組分成二組。依次類推，當分出來的小組只有一個數據時，可以認為這個小組組內已經達到了有序，然后再合并相鄰的二個小組就可以了。這樣通過先遞歸的分解數列，再合并數列就完成了歸并排序

歸并排序的時間復雜度，合并耗費O(n)時間，而由完全二叉樹的深度可知，整個歸并排序需要進行log_2n次，因此，總的時間復雜度為 O(nlogn)，而且這是歸并排序算法中最好、最壞、平均的時間性能。

由于歸并排序在歸并過程中需要與原始記錄序列同樣數量的存儲空間存放歸并結果 以及 遞歸時深度為 log_2n 的棧空間，因此空間復雜度為O(n+logn)。

另外，對代碼進行仔細研究，發現 Merge 函數中有if (L[i] 語句，這就說明它需要兩兩比較，不存在跳躍，因此歸并排序是一種穩定的排序算法。


也就是說，歸并排序是一種比較占用內存，但卻效率高且穩定的算法。

3.2 核心代碼

java 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

3.3 延伸

求逆序對

4冒泡排序

4.1 性能分析

時間復雜度O(n^2), 空間復雜度O(1)， 穩定，因為存在兩兩比較，不存在跳躍。

排序時間與輸入無關，最好，最差，平均都是O(n^2)

4.2 核心代碼

java     for(int i=0;i=i+1;j--){
                int temp;
                if(arraytoSort[j]

4.3 延伸

冒泡排序缺陷：


在排序過程中，執行完當前的第i趟排序后，可能數據已全部排序完備，但是程序無法判斷是否完成排序，會繼續執行剩下的(n-1-i)趟排序。解決方法： 設置一個flag位, 如果一趟無元素交換，則 flag = 0; 以后再也不進入第二層循環。
當排序的數據比較多時排序的時間會明顯延長，因為會比較 n*(n-1)/2次。

5. 堆排序

5.1 性能分析

時間復雜度 O(nlogn), 空間復雜度O(1). 從這一點就可以看出，堆排序在時間上類似歸并，但是它又是一種原地排序，時間復雜度小于歸并的O(n+logn)

排序時間與輸入無關，最好，最差，平均都是O(nlogn). 不穩定

堆排序借助了堆這個數據結構，堆類似二叉樹，又具有堆積的性質（子節點的關鍵值總小于（大于）父節點）

堆排序包括兩個主要操作:


保持堆的性質heapify(A,i)

時間復雜度O(logn)

建堆 buildmaxheap(A)

時間復雜度O(n)線性時間建堆

對于大數據的處理： 如果對100億條數據選擇Topk數據，選擇快速排序好還是堆排序好？ 答案是只能用堆排序。 堆排序只需要維護一個k大小的空間，即在內存開辟k大小的空間。而快速排序需要開辟能存儲100億條數據的空間，which is impossible.

5.2 核心代碼

javapublic 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(leftarray[left]){
                smallest = left;
            }
            else smallest = i;
        }
        if(rightarray[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

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 核心代碼

javapublic 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

非比較排序： ，計數排序，基數排序，桶排序，時間復雜度能夠達到O(n).  這些排序為了達到不比較的目的，對數據做了一些基本假設（限制）。如計數排序假設數據都[0,n] 范圍內，且范圍較小；基數排序假設數據都[0,n] 范圍內；也是桶排序假設數據均勻獨立的分布。

而且，非比較排序的空間要求比較高，用空間換取時間吧。當我們的待排序數組具備一些基數排序與桶排序要求的特性，且空間上又比較富裕時，桶排序與基數排序不失為最佳選擇。

7. 計數排序

我們希望能線性的時間復雜度排序，如果一個一個比較，顯然是不實際的，書上也在決策樹模型中論證了，比較排序的情況為nlogn 的復雜度。既然不能一個一個比較，我們想到一個辦法，就是如果在排序的時候就知道他的位置，那不就是掃描一遍，把他放入他應該的位置不就可以了。 要知道他的位置，我們只需要知道有多少不大于他不就可以了嗎？

7.1 性能分析

最好，最壞，平均的時間復雜度O(n+k), 天了嚕， 線性時間完成排序，且穩定。

優點：不需要比較函數，利用地址偏移，對范圍固定在[0,k]的整數排序的最佳選擇。是排序字節串最快的排序算法。

缺點：由于用來計數的數組的長度取決于待排序數組中數據的范圍（等于待排序數組的最大值與最小值的差加上1），這使得計數排序對于數據范圍很大的數組，需要大量時間和內存。

7.2 核心代碼

java    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=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 核心代碼

cRADIX-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

問題： 給定一個字符串數組，其中不同的串包含的字符數可能不同，但所有串中總的字符個數為 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排序非常好的文章

桶排序利用函數的映射關系，減少了幾乎所有的比較工作。實際上，桶排序的 f(k) 值的計算，其作用就相當于快排中劃分，已經把大量數據分割成了基本有序的數據塊 (桶)。然后只需要對桶中的少量數據做先進的比較排序即可。

對 N 個關鍵字進行桶排序的時間復雜度分為兩個部分：

(1) 循環計算每個關鍵字的桶映射函數，這個時間復雜度是 O(n)。

(2) 利用先進的比較排序算法對每個桶內的所有數據進行排序，其時間復雜度為  ∑ O(ni*logni) 。其中 ni 為第 i個桶的數據量。

很顯然，第 (2) 部分是桶排序性能好壞的決定因素。這就是一個時間代價和空間代價的權衡問題了。

9.2 核心代碼

9.3擴展



in summary



關于穩定性：


選擇排序、快速排序、希爾排序、堆排序不是穩定的排序算法，
冒泡排序、插入排序、歸并排序和基數排序是穩定的排序算法。
常用時間復雜度的大小關系：O(1)