摘要：數據結構與算法常用數據結構及其實現經過前面文章的鋪墊，我們鞏固了基礎數據結構的知識，接下來就可以進入算法的鞏固階段了。首先我們來看常見的排序算法。同樣的小規模數據轉換為插入排序會有效果提升。它只能對整數進行排序。

數據結構與算法——常用數據結構及其Java實現
經過前面文章的鋪墊，我們鞏固了基礎數據結構的知識，接下來就可以進入算法的鞏固階段了。首先我們來看常見的排序算法。

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

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

時間復雜度， 最好：正序O(n)、最壞：逆序O(n^2)、平均：O(n^2)
空間復雜度， O(1)
穩定性，因為相同的元素不會交換，所以是穩定的

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

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);//將本次最小值與已經排好序的隊列的最后一個元素交換
    }
}

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

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

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);//將未排序的第一個數據插入已排序的數據匯中的合適位置
        }
    }
}

時間復雜度， 最好：O(n)、最壞：O(n^2)、平均：O(n^2)。插入排序一般來說比選擇排序快，因為插入排序每次都是在已排序的數據中找（插入點），而選擇排序每次都是在未排序的數據中找（最小值），所以插入排序很好的利用了已有有序結果，當然更快。
空間復雜度， O(1)
穩定性，穩定，因為待插入元素和有序序列比較都是從最大值開始比較的，如果小于某個元素才放到該元素前面否則放該元素后面，也就是說，相同元素在有序隊列中的順序和其進入有序隊列的先后（也就是原本相對位置）是一致的

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

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;
    }
}

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

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

// 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);
}

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

原理：通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，然后分別對這兩部分記錄進行排序，以達到整個序列有序
具體操作：從數列中挑出一個元素，稱為 "基準"（pivot）；重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作；遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
所有代碼在這，關鍵代碼如下：

public static void sort(Comparable[] a) {
    StdRandom.shuffle(a);//打亂數組，消除輸入依賴
    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;
}

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

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

public static void sort(Comparable[] pq) {
    int n = pq.length;
    for (int k = n/2; k >= 1; k--)//構造堆，從最后一個有子節點的節點開始比較和下沉，直至根節點
        sink(pq, k, n);
    while (n > 1) {//堆排序
        exch(pq, 1, n--);//將最大值（根節點）和無序數組最后一元素交換，并將無序標志前移
        sink(pq, 1, 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++;//先比較左右子節點，找到較大的
        if (!less(pq, k, j)) break;//大于較大的子節點，無需下沉
        exch(pq, k, j);//否則下沉
        k = j;//繼續比較以這個節點為根的子樹
    }
}

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

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

private static int[] countSort(int[] A,int k){
    int[] C=new int[k+1];//構造C數組
    int length=A.length,sum=0;//獲取A數組大小用于構造B數組
    for (int anArray : A) { C[anArray] += 1;}// 統計A中各元素個數，存入C數組
    for(int i=0;i=0;i--){//倒序遍歷A數組（保證穩定性，因為相同的元素中靠后的個體的序號也相對較大），構造B數組
        B[C[A[i]]-1]=A[i];//將A中該元素放到排序后數組B中指定的位置
        C[A[i]]--;//將C中該元素-1，方便存放下一個同樣大小的元素
    }
    return B;//將排序好的數組返回，完成排序
}

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

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

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);
    }
    //桶數
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList());
    }
    //將每個元素放入桶
    for (int anArr : arr) {
        int num = (anArr - min) / (arr.length);
        bucketArr.get(num).add(anArr);
    }
    //對每個桶進行排序,調用自帶的排序
    for (ArrayList aBucketArr : bucketArr) {
        Collections.sort(aBucketArr);
    }
    //打印結果
    for (ArrayList anA : bucketArr) {StdOut.print(anA + "	"); }
    StdOut.println();
}

時間復雜度， 最好：O(n+k)、最壞：O(n^2)、平均：O(n+k)
空間復雜度， O(n+k)
穩定性，穩定，因為相同的元素肯定在同一個桶里，并且加入桶的順序和原順序一致

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

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