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

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

想更一進(jìn)步的支持我，請(qǐng)掃描下方的二維碼，你懂的~

時(shí)間復(fù)雜度O(n^2), 空間復(fù)雜度O(1)
排序時(shí)間與輸入有關(guān)：輸入的元素個(gè)數(shù)；元素已排序的程度。
最佳情況，輸入數(shù)組是已經(jīng)排好序的數(shù)組，運(yùn)行時(shí)間是n的線性函數(shù)； 最壞情況，輸入數(shù)組是逆序，運(yùn)行時(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 性能分析

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

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

原理：

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

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

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

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


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

3.2 核心代碼

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

時(shí)間復(fù)雜度O(n^2), 空間復(fù)雜度O(1)， 穩(wěn)定，因?yàn)榇嬖趦蓛杀容^，不存在跳躍。

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

4.2 核心代碼

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

4.3 延伸

冒泡排序缺陷：


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

5. 堆排序

5.1 性能分析

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

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

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

堆排序包括兩個(gè)主要操作:


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

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

建堆 buildmaxheap(A)

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

對(duì)于大數(shù)據(jù)的處理： 如果對(duì)100億條數(shù)據(jù)選擇Topk數(shù)據(jù)，選擇快速排序好還是堆排序好？ 答案是只能用堆排序。 堆排序只需要維護(hù)一個(gè)k大小的空間，即在內(nèi)存開(kāi)辟k大小的空間。而快速排序需要開(kāi)辟能存儲(chǔ)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)先級(jí)隊(duì)列，如作業(yè)調(diào)度。

6 快速排序

6.1 性能分析

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

時(shí)間復(fù)雜度：

最壞O（n^2） 當(dāng)劃分不均勻時(shí)候 逆序and排好序都是最壞情況

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

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

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

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

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

快速排序之所比較快，因?yàn)橄啾让芭菖判?，每次交換是跳躍式的。每次排序的時(shí)候設(shè)置一個(gè)基準(zhǔn)點(diǎn)，將小于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的左邊，將大于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的右邊。這樣在每次交換的時(shí)候就不會(huì)像冒泡排序一樣每次只能在相鄰的數(shù)之間進(jìn)行交換，交換的距離就大的多了。因此總的比較和交換次數(shù)就少了，速度自然就提高了。當(dāng)然在最壞的情況下，仍可能是相鄰的兩個(gè)數(shù)進(jìn)行了交換。因此快速排序的最差時(shí)間復(fù)雜度和冒泡排序是一樣的都是 O(n^2)，它的平均時(shí)間復(fù)雜度為 O(nlogn)。其實(shí)快速排序是基于 “二分” 的思想。

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

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

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

7. 計(jì)數(shù)排序

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

7.1 性能分析

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

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

缺點(diǎn)：由于用來(lái)計(jì)數(shù)的數(shù)組的長(zhǎng)度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時(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 擴(kuò)展

請(qǐng)給出一個(gè)算法，使之對(duì)給定的介于 0到 k 之間的 n個(gè)整數(shù)進(jìn)行預(yù)處理，并能在O(1) 時(shí)間內(nèi)回答出輸入的整數(shù)中有多少個(gè)落在 [a...b] 區(qū)間內(nèi)。你給出的算法的預(yù)處理時(shí)間為O(n+k)。

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

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

8 基數(shù)排序

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

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

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

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

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



8.1 性能分析

時(shí)間復(fù)雜度O（n） (實(shí)際上是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擴(kuò)展

問(wèn)題：對(duì)[0,n^2-1]的n 個(gè)整數(shù)進(jìn)行線性時(shí)間排序。

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

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

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

9. 桶排序

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

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

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

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

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



9.1 性能分析

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

桶排序的空間復(fù)雜度通常是比較高的，額外開(kāi)銷為O(n+m)（因?yàn)橐S護(hù) M 個(gè)數(shù)組的引用）。

就是桶越多，時(shí)間效率就越高，而桶越多，空間卻就越大，由此可見(jiàn)時(shí)間和空間是一個(gè)矛盾的兩個(gè)方面。

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

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

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

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

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

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

9.2 核心代碼

9.3擴(kuò)展



in summary



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


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