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

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

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

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

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 性能分析

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

排序時間與輸入無關(guān)，最佳情況，最壞情況都是如此, 穩(wěn)定。

原理：

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

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

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

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


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

3.2 核心代碼

java public int merge( int p, int q, int r ){
        int count = 0;
        int[] right = assignlist(p,q); 
        //賦值左半部分數(shù)組（賦值就是用for循環(huán)，還有一個哨兵：最后一個元素設(shè)置為maxvalue）
        int[] left = assignlist(q+1,r); //賦值有半部分數(shù)組
        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 延伸

求逆序?qū)?/p>

4冒泡排序

4.1 性能分析

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

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

4.2 核心代碼

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

4.3 延伸

冒泡排序缺陷：


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

5. 堆排序

5.1 性能分析

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

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

堆排序借助了堆這個數(shù)據(jù)結(jié)構(gòu)，堆類似二叉樹，又具有堆積的性質(zhì)（子節(jié)點的關(guān)鍵值總小于（大于）父節(jié)點）

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


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

時間復(fù)雜度O(logn)

建堆 buildmaxheap(A)

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

對于大數(shù)據(jù)的處理： 如果對100億條數(shù)據(jù)選擇Topk數(shù)據(jù)，選擇快速排序好還是堆排序好？ 答案是只能用堆排序。 堆排序只需要維護一個k大小的空間，即在內(nèi)存開辟k大小的空間。而快速排序需要開辟能存儲100億條數(shù)據(jù)的空間，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 延伸

堆這種數(shù)據(jù)結(jié)構(gòu)的很好的應(yīng)用是 優(yōu)先級隊列，如作業(yè)調(diào)度。

6 快速排序

6.1 性能分析

時間復(fù)雜度 O(nlogn)  空間復(fù)雜度O（logn） 不穩(wěn)定 【兩個時間復(fù)雜度O(nlogn) 的排序算法都不穩(wěn)定】

時間復(fù)雜度：

最壞O（n^2） 當劃分不均勻時候 逆序and排好序都是最壞情況

最好O（n） 當劃分均勻
partition的時間復(fù)雜度: O（n）一共需要logn次partition

空間復(fù)雜度：遞歸造成的?？臻g的使用，最好情況，遞歸樹的深度logn 空間復(fù)雜的logn，最壞情況，需要進行n‐1 遞歸調(diào)用，其空間復(fù)雜度為 O(n)，平均情況，空間復(fù)雜度也為O(log2n)。

由于關(guān)鍵字的比較和交換是跳躍進行的，因此，快速排序是一種不穩(wěn)定的排序方法。

快速排序的每一輪就是將這一輪的基準數(shù)歸位，直到所有的數(shù)都歸為為止，排序結(jié)束。（類似冒泡）.

partition是返回一個基準值的index, index 左邊都小于該index的數(shù)，右邊都大于該index的數(shù)。

快速排序之所比較快，因為相比冒泡排序，每次交換是跳躍式的。每次排序的時候設(shè)置一個基準點，將小于等于基準點的數(shù)全部放到基準點的左邊，將大于等于基準點的數(shù)全部放到基準點的右邊。這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數(shù)之間進行交換，交換的距離就大的多了。因此總的比較和交換次數(shù)就少了，速度自然就提高了。當然在最壞的情況下，仍可能是相鄰的兩個數(shù)進行了交換。因此快速排序的最差時間復(fù)雜度和冒泡排序是一樣的都是 O(n^2)，它的平均時間復(fù)雜度為 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

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

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

7. 計數(shù)排序

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

7.1 性能分析

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

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

缺點：由于用來計數(shù)的數(shù)組的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時間和內(nèi)存。

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個整數(shù)進行預(yù)處理，并能在O(1) 時間內(nèi)回答出輸入的整數(shù)中有多少個落在 [a...b] 區(qū)間內(nèi)。你給出的算法的預(yù)處理時間為O(n+k)。

分析：就是用計數(shù)排序中的預(yù)處理方法，獲得數(shù)組 C[0...k]，使得C[i]為不大于 i的元素的個數(shù)。這樣落入 [a...b] 區(qū)間內(nèi)的元素個數(shù)有 C[b]-C[a-1]。

計數(shù)排序的重要性質(zhì)是他是穩(wěn)定的。一般而言，僅當衛(wèi)星數(shù)據(jù)隨著被排序的元素一起移動時，穩(wěn)定性才顯得比較重要。而這也是計數(shù)排序作為基數(shù)排序的子過程的重要原因

8 基數(shù)排序

為什么要用基數(shù)排序 ？

計數(shù)排序和桶排序都只是在研究一個關(guān)鍵字的排序，現(xiàn)在我們來討論有多個關(guān)鍵字的排序問題。

假設(shè)我們有一些二元組(a,b)，要對它們進行以a 為首要關(guān)鍵字，b的次要關(guān)鍵字的排序。我們可以先把它們先按照首要關(guān)鍵字排序，分成首要關(guān)鍵字相同的若干堆。然后，在按照次要關(guān)鍵值分別對每一堆進行多帶帶排序。最后再把這些堆串連到一起，使首要關(guān)鍵字較小的一堆排在上面。按這種方式的基數(shù)排序稱為 MSD(Most Significant Dight) 排序。

第二種方式是從最低有效關(guān)鍵字開始排序，稱為 LSD(Least Significant Dight)排序 。首先對所有的數(shù)據(jù)按照次要關(guān)鍵字排序，然后對所有的數(shù)據(jù)按照首要關(guān)鍵字排序。要注意的是，使用的排序算法必須是穩(wěn)定的，否則就會取消前一次排序的結(jié)果。由于不需要分堆對每堆多帶帶排序，LSD 方法往往比 MSD 簡單而開銷小。下文介紹的方法全部是基于 LSD 的。

通常，基數(shù)排序要用到計數(shù)排序或者桶排序。使用計數(shù)排序時，需要的是Order數(shù)組。使用桶排序時，可以用鏈表的方法直接求出排序后的順序。



8.1 性能分析

時間復(fù)雜度O（n） (實際上是O(d(n+k)) d是位數(shù))

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 個整數(shù)進行線性時間排序。

思路 ： 把整數(shù)轉(zhuǎn)換為n進制再排序，每個數(shù)有兩位，每位的取值范圍是[0..n-1]，再進行基數(shù)排序

http://blog.csdn.net/mishifangxiangdefeng/article/details/7685839

問題： 給定一個字符串數(shù)組，其中不同的串包含的字符數(shù)可能不同，但所有串中總的字符個數(shù)為 n。說明如何在 O(n) 時間內(nèi)對該數(shù)組進行排序

9. 桶排序

桶排序的思想近乎徹底的分治思想。

桶排序假設(shè)待排序的一組數(shù)均勻獨立的分布在一個范圍中，并將這一范圍劃分成幾個子范圍（桶）。

然后基于某種映射函數(shù)f ，將待排序列的關(guān)鍵字 k 映射到第i個桶中 (即桶數(shù)組B 的下標i) ，那么該關(guān)鍵字k 就作為 B[i]中的元素 (每個桶B[i]都是一組大小為N/M 的序列 )。

接著將各個桶中的數(shù)據(jù)有序的合并起來 : 對每個桶B[i] 中的所有元素進行比較排序 (可以使用快排)。然后依次枚舉輸出 B[0]....B[M] 中的全部內(nèi)容即是一個有序序列。

補充： 映射函數(shù)一般是 f = array[i] / k; k^2 = n; n是所有元素個數(shù)



9.1 性能分析

平均時間復(fù)雜度為線性的 O(n+C) 最優(yōu)情形下，桶排序的時間復(fù)雜度為O(n)。

桶排序的空間復(fù)雜度通常是比較高的，額外開銷為O(n+m)（因為要維護 M 個數(shù)組的引用）。

就是桶越多，時間效率就越高，而桶越多，空間卻就越大，由此可見時間和空間是一個矛盾的兩個方面。

算法穩(wěn)定性 : 桶排序的穩(wěn)定性依賴于桶內(nèi)排序。如果我們使用了快排，顯然，算法是不穩(wěn)定的。
一個講bucket排序非常好的文章

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

對 N 個關(guān)鍵字進行桶排序的時間復(fù)雜度分為兩個部分：

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

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

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

9.2 核心代碼

9.3擴展



in summary



關(guān)于穩(wěn)定性：


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