摘要：數(shù)據(jù)結(jié)構(gòu)與算法常用數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)經(jīng)過前面文章的鋪墊，我們鞏固了基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的知識，接下來就可以進(jìn)入算法的鞏固階段了。首先我們來看常見的排序算法。同樣的小規(guī)模數(shù)據(jù)轉(zhuǎn)換為插入排序會有效果提升。它只能對整數(shù)進(jìn)行排序。

數(shù)據(jù)結(jié)構(gòu)與算法——常用數(shù)據(jù)結(jié)構(gòu)及其Java實(shí)現(xiàn)
經(jīng)過前面文章的鋪墊，我們鞏固了基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的知識，接下來就可以進(jìn)入算法的鞏固階段了。首先我們來看常見的排序算法。

原理：依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面（左邊），大數(shù)放在后面（右邊），就像冒泡一樣
具體操作：第一趟，首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，這樣第一趟下來最大的數(shù)就在最后一位了。然后還是從第一個(gè)數(shù)開始重復(fù)第一趟步驟比較，但是這次不比較最后一個(gè)數(shù)了，第二趟結(jié)束后第二大的數(shù)就在倒數(shù)第二位......以此類推，直至全部排序完成。
所有代碼在這，關(guān)鍵代碼如下：

private static void sort(Comparable[] a) throws IllegalAccessException, InstantiationException {
    Object tmp;
    boolean noChange = false;//用來標(biāo)識輸入序列的排序情況，
    for (int i = 0;i0){
                tmp =  a[j];
                a[j] = a[j+1];
                a[j+1] = (Comparable) tmp;
                noChange = false;//有交換
            }
        }
        System.out.println(noChange);//展示跑了多少趟,幾個(gè)打印就對應(yīng)幾趟
    }
}

時(shí)間復(fù)雜度， 最好：正序O(n)、最壞：逆序O(n^2)、平均：O(n^2)
空間復(fù)雜度， O(1)
穩(wěn)定性，因?yàn)橄嗤脑夭粫粨Q，所以是穩(wěn)定的

原理：每次選擇未排序序列中的最小元素。
具體操作：首先在未排序序列中找到最小元素，放到序列的起始位置，然后從剩余未排序元素中尋找最小元素放到已排序序列的末尾，以此類推，直至排序完畢。
所有代碼在這，關(guān)鍵代碼如下：

public static void sort(Comparable[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++) {
        int min = i;
        for (int j = i+1; j < n; j++) {
            if (less(a[j], a[min])) min = j;//找到剩下元素的最小值
        }
        exch(a, i, min);//將本次最小值與已經(jīng)排好序的隊(duì)列的最后一個(gè)元素交換
    }
}

時(shí)間復(fù)雜度， 都是：O(n^2)
空間復(fù)雜度， O(1)
穩(wěn)定性，不穩(wěn)定。舉個(gè)例子，序列5 8 5 2 9， 第一遍選擇第1個(gè)元素5會和2交換，那么原序列中2個(gè)5的相對前后順序就被破壞了

原理：將未排序的序列中的每一個(gè)數(shù)據(jù)依次按合理的順序插入已排列的數(shù)據(jù)中。
具體操作：構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從頭掃描，找到相應(yīng)位置并插入。第一趟第一個(gè)就是有序數(shù)據(jù)，第二趟把第二個(gè)數(shù)據(jù)和第一個(gè)有序數(shù)據(jù)排序，第三趟把第三個(gè)數(shù)據(jù)和一、二個(gè)有序數(shù)據(jù)排序，以此類推直至排序完畢。
所有代碼在這，關(guān)鍵代碼如下：

public static void sort(Comparable[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++) {
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            exch(a, j, j-1);//將未排序的第一個(gè)數(shù)據(jù)插入已排序的數(shù)據(jù)匯中的合適位置
        }
    }
}

時(shí)間復(fù)雜度， 最好：O(n)、最壞：O(n^2)、平均：O(n^2)。插入排序一般來說比選擇排序快，因?yàn)椴迦肱判蛎看味际窃谝雅判虻臄?shù)據(jù)中找（插入點(diǎn)），而選擇排序每次都是在未排序的數(shù)據(jù)中找（最小值），所以插入排序很好的利用了已有有序結(jié)果，當(dāng)然更快。
空間復(fù)雜度， O(1)
穩(wěn)定性，穩(wěn)定，因?yàn)榇迦朐睾陀行蛐蛄斜容^都是從最大值開始比較的，如果小于某個(gè)元素才放到該元素前面否則放該元素后面，也就是說，相同元素在有序隊(duì)列中的順序和其進(jìn)入有序隊(duì)列的先后（也就是原本相對位置）是一致的

原理：使數(shù)組中的任意間隔為 h 的元素都是有序的
具體操作：選擇一個(gè)遞增的增量序列t1，t2，…，tk，tk=1；按增量序列個(gè)數(shù)k，對序列進(jìn)行k 趟排序；每趟排序，根據(jù)對應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子序列進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長度即為整個(gè)序列的長度。
所有代碼在這，關(guān)鍵代碼如下：

public static void sort(Comparable[] a) {
    int n = a.length;

    // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ... 
    int h = 1;
    while (h < n/3) h = 3*h + 1; 

    while (h >= 1) {
        // h-sort the array
        for (int i = h; i < n; i++) {
            for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                exch(a, j, j-h);
            }
        }
        h /= 3;
    }
}

時(shí)間復(fù)雜度， 具體取決于間隔 h，最好：O(nlogn)、最壞：O(n^2)、平均：無。希爾算法的性能與h有很大關(guān)系。只對特定的待排序記錄序列，可以準(zhǔn)確地估算關(guān)鍵詞的比較次數(shù)和對象移動次數(shù)。想要弄清關(guān)鍵詞比較次數(shù)和記錄移動次數(shù)與h選擇之間的關(guān)系，并給出完整的數(shù)學(xué)分析，至今仍然是數(shù)學(xué)難題。
空間復(fù)雜度， O(1)
穩(wěn)定性，一次插入排序是穩(wěn)定的，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，shell排序每個(gè)不同的增量都是插入排序，有多次，實(shí)際上是分組插入排序（又叫縮小增量排序），所以是不穩(wěn)定的。

原理：將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。
具體操作：把長度為n的輸入序列分成兩個(gè)長度為n/2的子序列；對這兩個(gè)子序列分別遞歸調(diào)用歸并排序（終止條件是只有1個(gè)元素的最小子序列，兩個(gè)最小子序列直接merge）；將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。
所有代碼在這，關(guān)鍵代碼如下：

// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
    assert isSorted(a, lo, mid);
    assert isSorted(a, mid+1, hi);

    // copy to aux[]
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k]; 
    }

    // merge back to a[]
    int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if      (i > mid)              a[k] = aux[j++];
        else if (j > hi)               a[k] = aux[i++];
        else if (less(aux[j], aux[i])) a[k] = aux[j++];
        else                           a[k] = aux[i++];
    }

    // postcondition: a[lo .. hi] is sorted
    assert isSorted(a, lo, hi);
}

時(shí)間復(fù)雜度， 都是：O(nlogn)。通過使用插入排序來處理小規(guī)模子序列(如長度小于15)一般可以提升歸并排序的效率10%~15%
空間復(fù)雜度， O(n)
穩(wěn)定性，穩(wěn)定

原理：通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，然后分別對這兩部分記錄進(jìn)行排序，以達(dá)到整個(gè)序列有序
具體操作：從數(shù)列中挑出一個(gè)元素，稱為 "基準(zhǔn)"（pivot）；重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作；遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
所有代碼在這，關(guān)鍵代碼如下：

public static void sort(Comparable[] a) {
    StdRandom.shuffle(a);//打亂數(shù)組，消除輸入依賴
    sort(a, 0, a.length - 1);
    assert isSorted(a);
}

// quicksort the subarray from a[lo] to a[hi]
private static void sort(Comparable[] a, int lo, int hi) { 
    if (hi <= lo) return;
    int j = partition(a, lo, hi);
    sort(a, lo, j-1);
    sort(a, j+1, hi);
    assert isSorted(a, lo, hi);
}

// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
// and return the index j.
private static int partition(Comparable[] a, int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    Comparable v = a[lo];
    while (true) { 

        // find item on lo to swap
        while (less(a[++i], v))
            if (i == hi) break;

        // find item on hi to swap
        while (less(v, a[--j]))
            if (j == lo) break;      // redundant since a[lo] acts as sentinel

        // check if pointers cross
        if (i >= j) break;

        exch(a, i, j);
    }

    // put partitioning item v at a[j]
    exch(a, lo, j);

    // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
    return j;
}

時(shí)間復(fù)雜度， 最好：O(nlogn)、最壞：O(n^2)、平均：O(nlogn)。一般快于歸并排序，雖然比較次數(shù)可能多些，但是移動數(shù)據(jù)次數(shù)更少。同樣的小規(guī)模數(shù)據(jù)轉(zhuǎn)換為插入排序會有效果提升。對于包含大量重復(fù)元素的數(shù)據(jù)，使用三向切分也能提高性能。
空間復(fù)雜度， 最好：每次劃分都在中間O(logn)、最壞：退化為冒泡O(n)
穩(wěn)定性，不穩(wěn)定，比如序列為 5 3 3 4 3 8 9 10 11， 現(xiàn)在中樞元素5和3(第5個(gè)元素，下標(biāo)從1開始計(jì))交換就會把元素3的穩(wěn)定性打亂，所以快速排序是一個(gè)不穩(wěn)定的排序算法，不穩(wěn)定發(fā)生在中樞元素和a[j] 交換的時(shí)刻

原理：利用堆這種數(shù)據(jù)結(jié)構(gòu)的一種排序算法，堆是一個(gè)近似完全二叉樹的結(jié)構(gòu)，滿足堆的性質(zhì)：即子結(jié)點(diǎn)的鍵總是小于（或者大于）它的父節(jié)點(diǎn)
具體操作：將初始待排序關(guān)鍵字序列(R1,R2....Rn)構(gòu)建成大頂堆，此堆為初始的無序區(qū)； 將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無序區(qū)(R1,R2,......Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2...n-1]<=R[n]； 由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對當(dāng)前無序區(qū)(R1,R2,......Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個(gè)元素交換，得到新的無序區(qū)(R1,R2....Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過程完成。
所有代碼在這，堆的相關(guān)代碼,關(guān)鍵代碼如下：

public static void sort(Comparable[] pq) {
    int n = pq.length;
    for (int k = n/2; k >= 1; k--)//構(gòu)造堆，從最后一個(gè)有子節(jié)點(diǎn)的節(jié)點(diǎn)開始比較和下沉，直至根節(jié)點(diǎn)
        sink(pq, k, n);
    while (n > 1) {//堆排序
        exch(pq, 1, n--);//將最大值（根節(jié)點(diǎn)）和無序數(shù)組最后一元素交換，并將無序標(biāo)志前移
        sink(pq, 1, n);//下沉交換后的根節(jié)點(diǎn)
    }
}

private static void sink(Comparable[] pq, int k, int n) {
    while (2*k <= n) {
        int j = 2*k;
        if (j < n && less(pq, j, j+1)) j++;//先比較左右子節(jié)點(diǎn)，找到較大的
        if (!less(pq, k, j)) break;//大于較大的子節(jié)點(diǎn)，無需下沉
        exch(pq, k, j);//否則下沉
        k = j;//繼續(xù)比較以這個(gè)節(jié)點(diǎn)為根的子樹
    }
}

時(shí)間復(fù)雜度， 都是：O(nlogn)
空間復(fù)雜度， O(1)
穩(wěn)定性，比如：3 27 36 27，堆頂3先輸出，則第三層的27（最后一個(gè)27）跑到堆頂，然后堆穩(wěn)定，繼續(xù)輸出堆頂，是剛才那個(gè)27，這樣說明后面的27先于第二個(gè)位置的27輸出，不穩(wěn)定

原理：使用一個(gè)額外的數(shù)組C，其中第i個(gè)元素是待排序數(shù)組A中值等于i的元素的個(gè)數(shù)。然后根據(jù)數(shù)組C來將A中的元素排到正確的位置。它只能對整數(shù)進(jìn)行排序。不是比較排序，排序的速度快于任何比較排序算法
具體操作：找出待排序的數(shù)組中最大和最小的元素；統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)；對所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）；反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1。
所有代碼在這，關(guān)鍵代碼如下：

private static int[] countSort(int[] A,int k){
    int[] C=new int[k+1];//構(gòu)造C數(shù)組
    int length=A.length,sum=0;//獲取A數(shù)組大小用于構(gòu)造B數(shù)組
    for (int anArray : A) { C[anArray] += 1;}// 統(tǒng)計(jì)A中各元素個(gè)數(shù)，存入C數(shù)組
    for(int i=0;i=0;i--){//倒序遍歷A數(shù)組（保證穩(wěn)定性，因?yàn)橄嗤脑刂锌亢蟮膫€(gè)體的序號也相對較大），構(gòu)造B數(shù)組
        B[C[A[i]]-1]=A[i];//將A中該元素放到排序后數(shù)組B中指定的位置
        C[A[i]]--;//將C中該元素-1，方便存放下一個(gè)同樣大小的元素
    }
    return B;//將排序好的數(shù)組返回，完成排序
}

時(shí)間復(fù)雜度， 都是：O(n+k)，（輸入的元素是n 個(gè)0到k之間的整數(shù)）
空間復(fù)雜度， O(k)
穩(wěn)定性，穩(wěn)定

原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)量的桶里，每個(gè)桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排）
具體操作： 設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶；遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)一個(gè)一個(gè)放到對應(yīng)的桶里去；對每個(gè)不是空的桶進(jìn)行排序；從不是空的桶里把排好序的數(shù)據(jù)拼接起來。
所有代碼在這，關(guān)鍵代碼如下：

private static void bucketSort(int[] arr){
    int max = Integer.MIN_VALUE,min = Integer.MAX_VALUE;
    for (int anArr : arr) {
        max = Math.max(max, anArr);
        min = Math.min(min, anArr);
    }
    //桶數(shù)
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList());
    }
    //將每個(gè)元素放入桶
    for (int anArr : arr) {
        int num = (anArr - min) / (arr.length);
        bucketArr.get(num).add(anArr);
    }
    //對每個(gè)桶進(jìn)行排序,調(diào)用自帶的排序
    for (ArrayList aBucketArr : bucketArr) {
        Collections.sort(aBucketArr);
    }
    //打印結(jié)果
    for (ArrayList anA : bucketArr) {StdOut.print(anA + "	"); }
    StdOut.println();
}

時(shí)間復(fù)雜度， 最好：O(n+k)、最壞：O(n^2)、平均：O(n+k)
空間復(fù)雜度， O(n+k)
穩(wěn)定性，穩(wěn)定，因?yàn)橄嗤脑乜隙ㄔ谕粋€(gè)桶里，并且加入桶的順序和原順序一致

原理：將待排序數(shù)據(jù)拆分成多個(gè)關(guān)鍵字進(jìn)行排序，基數(shù)排序的實(shí)質(zhì)是多關(guān)鍵字排序，將待排數(shù)據(jù)里的關(guān)鍵字拆分成多個(gè)排序關(guān)鍵字，第1個(gè)排序關(guān)鍵字，第2個(gè)排序關(guān)鍵字，......,第k個(gè)排序關(guān)鍵字,然后根據(jù)子關(guān)鍵字對待排序數(shù)據(jù)進(jìn)行排序（必須借助于另一種排序方法，而且這種排序方法必須是穩(wěn)定的）
具體操作：取得數(shù)組中的最大數(shù)，并取得位數(shù)；arr為原始數(shù)組，從最低位開始取每個(gè)位組成radix數(shù)組；對radix進(jìn)行排序；換句話說，第一輪下來，數(shù)組按照個(gè)位有序，第二輪下來數(shù)組按照十位有序，依次類推，由于子關(guān)鍵字排序穩(wěn)定所以最終的數(shù)組是有序的
所有代碼在這，關(guān)鍵代碼如下：

private static void radixSort(int[] array,int d){
    int n=1;//代表位數(shù)對應(yīng)的數(shù)：1,10,100...
    int k=0;//保存每一位排序后的結(jié)果用于下一位的排序輸入
    int length=array.length;
    int[][] bucket=new int[10][length];//二維數(shù)組排序桶，用于保存每次排序后的結(jié)果，這一位上排序結(jié)果相同的數(shù)字放在同一個(gè)桶里
    int[] order=new int[length];//用于保存每個(gè)桶里有多少個(gè)數(shù)字，默認(rèn)初始化為0
    while(n
時(shí)間復(fù)雜度， 都是：O(nxk)
空間復(fù)雜度， O(nxk)
穩(wěn)定性，穩(wěn)定
參考
本書大部分代碼來自于算法第四版；
http://www.cnblogs.com/jztan/...；
https://www.cnblogs.com/devel...；
百度百科；
http://blog.csdn.net/apei830/...；
https://www.cnblogs.com/devel...；
訪問原文。算法博大精深，這里把各種排序算法總結(jié)，如有錯(cuò)誤請輕拍~