數(shù)據(jù)結(jié)構(gòu)與算法之排序

通過前面的知識，我們已經(jīng)知道，有序的數(shù)據(jù)在查找時有極大的性能提升。很多查找都基于有序數(shù)據(jù)，但并不是所有的結(jié)構(gòu)都能像二叉排序樹一樣，在插入數(shù)據(jù)時就已經(jīng)排好序，很多時候往往是無序的數(shù)據(jù)，需要我們使用時再進(jìn)行排序，這就意味著我們需要尋找高效率的排序算法。接下來，我們對當(dāng)下使用較為普遍的幾個算法逐一進(jìn)行分析。這里推薦一個可以查看算法運行動態(tài)過程的網(wǎng)站，加深對算法原理的理解。

基礎(chǔ)知識

排序定義

假設(shè)含有n個記錄的序列為{r1. r2, ..., rn}，其相應(yīng)的關(guān)鍵字分別為{k1, k2, ..., kn}，需確定1, 2, ..., n的一種排列p1, p2, ..., pn，使其相應(yīng)的關(guān)鍵字滿足kp1≤kp2≤...≤kpn(非遞減或非遞增) 關(guān)系，即使得序列成為一個按關(guān)鍵字有序的序列{rp1, rp2, ..., rpn} ， 這樣的操作就稱為排序。

穩(wěn)定性

假設(shè)ki=kj( 1≤i≤n, 1≤j≤ n, i≠j ) ，且在排序前的序列中 ri 領(lǐng)先于 rj (即i<j) 。如果排序后 ri 仍領(lǐng)先于 rj，則稱所用的排序方法是穩(wěn)定的；反之，若可能使得排序后的序列中 rj 領(lǐng)先 ri，則稱所用的排序方法是不穩(wěn)定的。

簡單來說，就是對于原數(shù)據(jù)中相等的數(shù)據(jù)，排序前后如果相對位置沒有改變，就是穩(wěn)定的。

內(nèi)排序與外排序

內(nèi)排序是在排序整個過程中，待排序的所有記錄全部被放置在內(nèi)存中。外排序是由于排序的記錄個數(shù)太多，不能同時放置在內(nèi)存，整個排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能進(jìn)行。本文先介紹內(nèi)排序算法，外排序以后再來分析。

冒泡排序

冒泡排序（Bubble Sort）是一種交換排序，它的基本思想是：兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，直到?jīng)]有反序的記錄為止。

冒泡排序可能是我們最熟悉的排序算法了，它的核心在于兩兩交換，代碼代碼：

private void bubbleSort(int[] arr){
    int len = arr.length;

    for (int i = 0; i < len-1; i++) {
        for (int j=0; j < len-1-i; j++) {
            if(arr[j]>arr[j+1]){
                swap(arr, j, j+1);
            }
        }
    }
}

它的最壞時間復(fù)雜度是1+2+...+(n-1) = n(n-1)/2，也就是O(n2)，這個復(fù)雜度相對還是比較高的，所以只適合小量數(shù)據(jù)排序。因為冒泡排序每次遍歷后，最后的數(shù)據(jù)一定是有序的，所以當(dāng)初始數(shù)據(jù)部分有序時，還可以對它進(jìn)行優(yōu)化。比如數(shù)組為{1,0,5,6,7,8,9,10}，當(dāng)?shù)谝淮伪闅v后，數(shù)組就是有序的，這時后續(xù)的循環(huán)遍歷都是沒有用的，優(yōu)化后的算法如下：

private void bubbleSort1(int[] arr){
    int len = arr.length;
    boolean flag = false;
    for (int i = 0; i < len-1; i++) {
        flag = false;
        for (int j=0; j < len-1-i; j++) {
            if(arr[j]>arr[j+1]){
                swap(arr, j, j+1);
                flag = true;
            }
        }
    }
}

使用一個flag標(biāo)記是否有數(shù)據(jù)交換，冒泡排序如果沒有數(shù)據(jù)交換，則意味著后邊的數(shù)據(jù)一定是有序的，這樣一來可以有效地提高冒泡排序的性能。但總體而言，冒泡排序還是不適合大數(shù)據(jù)量、數(shù)據(jù)比較亂的情況。

簡單選擇排序

選擇排序的思想是每一趟從待排序的記錄中選出最小的元素，順序放在已排好序的序列最后，直到全部記錄排序完畢。簡單選擇排序就基于此思想，除此之外還有樹型選擇排序和堆排序也是基于此思想。

簡單選擇排序法就是通過n-i次關(guān)鍵字間的比較，從n-i+1個記錄中選出關(guān)鍵字最小的記錄，并和第 i (0≤i≤n)個記錄交換。

它的實現(xiàn)如下：

private void selectSort(int[] arr){
    int len = arr.length;
    int min;
    for (int i = 0; i < len; i++) {
        min = i;
        for (int j = i+1; j < len; j++) {
            if(arr[min]>arr[j]){
                min = j;
            }
        }
        if(i!=min){
            swap(arr,i,min);
        }
    }
}

總體來看，簡單排序算法的最壞時間復(fù)雜度也是O(n2)，但是它交換數(shù)據(jù)的次數(shù)明顯比冒泡排序要少很多，所以性能也比冒泡排序略優(yōu)。

直接插入排序

直接插入排序和我們排序撲克牌的道理一致，就是把新的一張牌插入到已經(jīng)排好序的牌中，它的基本操作是將一個記錄插入到已經(jīng)排好序的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。它的代碼實現(xiàn)如下：

private void insertSort(int[] arr){
    int len = arr.length;
    int temp;
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < i; j++) {
            if(arr[i]<arr[j]){
                temp = arr[i];
                // j及以后的記錄向后移動一位，然后把當(dāng)前值存放在j的位置
                System.arraycopy(arr,j,arr,j+1,i-j);
                arr[j] = temp;
            }
        }
    }
}

它的最壞時間復(fù)雜度依然是O(n2)。

我們介紹了三種最簡單，最容易理解的算法，但是它們的效率也確實較低。在數(shù)據(jù)量小的時候影響不大，然而現(xiàn)實是我們更多地要對大量數(shù)據(jù)進(jìn)行排序。接下來介紹的幾種算法屬于改進(jìn)算法，它們的效率都較為高一些。

希爾排序

簡單的排序算法，都需要在數(shù)據(jù)量少，或者部分有序的情況下，才能發(fā)揮較好的性能。但是再大規(guī)模的數(shù)據(jù)都可以拆分成多個小規(guī)模的數(shù)據(jù)，希爾排序的思想就是把大規(guī)模的數(shù)據(jù)拆分成多個小規(guī)模數(shù)據(jù)，然后每部分分別進(jìn)行直接插入排序，最后再對全部數(shù)據(jù)進(jìn)行整體排序。如何拆分就是希爾排序的重點，比如數(shù)據(jù)是{0, 9, 2, 4, 6, 1}，要將它拆成兩部分，如果按照前后拆分，那么進(jìn)行直接插入排序后結(jié)果是{0, 2, 9, 1, 4, 6}，這樣排序后對后續(xù)整體排序沒有幫助。那么希爾排序是如何做的呢？我們先通過一個簡單的數(shù)組來演示希爾排序的過程，首先有數(shù)組如下：

希爾排序

假設(shè)第一次取數(shù)據(jù)的一半作為間隔值，之后每次減半，我們把這個值記為inc，那么第一次inc=5，我們在對應(yīng)位置前加一條紅色虛線表示，如下所示：

inc定義

接下來我們就要進(jìn)行直接插入排序了，前面說過希爾排序不是按照前后區(qū)分，而是按照間隔區(qū)分的，所以，在進(jìn)行完這一輪的排序后，我們要保證以下數(shù)據(jù)是有序的，如下圖所示，不同顏色表示不同的子數(shù)組，只要保證每個子數(shù)組有序即可：

子數(shù)組拆分

可以看到，每個子數(shù)組的元素下標(biāo)間隔都是inc，這就是inc值的意義。根據(jù)這一原則，我們就可以進(jìn)行直接插入排序了，只需要依次將每個子數(shù)組排好序即可。首先比較0和5位置的值，發(fā)現(xiàn)已經(jīng)有序，無需交換，如下：

比較0和5

然后比較位置1和6，發(fā)現(xiàn)數(shù)值順序錯誤，對它進(jìn)行交換，如下所示：

比較1和6

接下來再依次比較2和7，3和8，4和9的值，將其排序，最終結(jié)果如下所示：

第一輪比較結(jié)果

現(xiàn)在，拆分的子數(shù)組都已經(jīng)是有序了。接下來，我們需要合并，我們把inc的值折半，再進(jìn)行上述操作，那么inc的位置和拆分的子數(shù)組如下所示：

子數(shù)組拆分

可以看到，每個子數(shù)組的元素下標(biāo)間隔都和inc值一樣，這時子數(shù)組只有兩個了。我們來對這兩個子數(shù)據(jù)依次進(jìn)行直接插入排序，首先對包含位置0的數(shù)組進(jìn)行排序，直接插入排序就是把當(dāng)前值插入到已有的有序子數(shù)組中，所以0位置依然是0，然后把位置2的元素插入，因為1＞0，所以它的位置不變，如下所示：

調(diào)整位置0和2

位置4和6的元素又是最大值，所以也不需要交換，結(jié)果如下所示：

調(diào)整位置4和6

接下來位置8，插入后需要和6交換，如下所示：

調(diào)整位置8

這樣，第一個數(shù)組就調(diào)整完畢了，接下來調(diào)整第二個數(shù)組，位置1和3需要交換，如下所示：

調(diào)整位置1和3

接下來調(diào)整位置5，因為值3是最小值，應(yīng)該放在位置1，所以需要把1和3位置的值向后移動，然后再插入，結(jié)果如下：

調(diào)整位置5

最后位置7和9也按照同樣的方式進(jìn)行，最終結(jié)果如下：

調(diào)整位置7和9

現(xiàn)在，我們再進(jìn)行合并時就是一個完整的數(shù)組了，可以看到，這個數(shù)組已經(jīng)是基本有序的了，較小的值基本位于左側(cè)，較大的值基本位于右側(cè)，這比直接進(jìn)行直接插入排序要好的多。希爾排序的代碼如下：

private void shellSort(int[] arr){
    int len = arr.length;
    int inc = len;
    // 設(shè)置間隔值
    for (inc=len/2; inc>0; inc/=2) {
        // i 從inc走到len，j正好可以把所有子數(shù)組遍歷一次
        // j會先比較每個子數(shù)組的第一個值，再第二個值，這樣橫向進(jìn)行遍歷
        for (int i = inc; i < len; i++) {
            for (int j = i; j>=inc && arr[j]<arr[j-inc]; j-=inc) {
                swap(arr,j,j-inc);
            }
        }
    }
}

希爾排序總體而言效率比直接插入排序要好，因為它最開始當(dāng)inc值較大時，數(shù)據(jù)的移動距離很長，而當(dāng)inc值小時，因為數(shù)據(jù)已經(jīng)大致有序，可以使直接插入排序更有效率，這兩點是希爾排序高效必備的條件。inc值的選取對希爾排序十分關(guān)鍵，像以上這種折半方式，在某些情況下還是較慢，但是我們沒有辦法找到完美的計算方案使希爾排序最高效，以inc=inc*3+1構(gòu)建的間隔也是常用的一種，示例代碼如下：

private void shellSort1(int[] arr) {
    //首先根據(jù)數(shù)組的長度確定增量的最大值
    int inc=1;
    // inc * 3 + 1得到增量序列的最大值
    while(inc <= arr.length / 3)
        inc = inc * 3 + 1;
    //進(jìn)行增量查找和排序
    while(inc>=1){           
        for(int i=inc;i<arr.length;i++){
            for(int j=i;j >= inc && arr[j] < arr[j-inc];j -= inc){
                swap(arr,j,j-inc);
            }
        }
        inc = inc/3;
    } 
}

目前，最高效的希爾排序的時間復(fù)雜度可以達(dá)到O(n3/2)，相關(guān)知識大家可以查閱書籍了解，這里我們就不再追究了。

堆排序

堆排序是對簡單選擇排序的優(yōu)化，在簡單選擇排序中，每排序一個數(shù)據(jù)，都要在剩余全部數(shù)據(jù)中尋找最小值，但是在這個尋找的過程中，沒有對剩余的數(shù)據(jù)記錄，所以之后的尋找會進(jìn)行多次重復(fù)操作。堆排序則是會把這些數(shù)據(jù)記錄在堆中，之后的尋找只需要在堆中進(jìn)行。

堆是具有下列性質(zhì)的完全二叉樹：每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值，稱為大頂堆；或者每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值，稱為小頂堆。

根據(jù)以上定義，可以確定，根結(jié)點一定是最大（或最?。┲?。大頂堆和小頂堆示意如下：

大頂堆
小頂堆

如果按照層序遍歷的順序給堆的每個結(jié)點編號：0, 1, ..., (n-1)，那么它一定符合以下條件：

a[i]≤a[2i+1] 且 a[i]≤a[2i+2]，其中0 ≤ i ≤ (n-1)/2，或 a[i]≥a[2i+1] 且 a[i]≥a[2i+2]，其中0 ≤ i ≤ (n-1)/2。

掌握了堆的概念之后，就可以進(jìn)行堆排序了，以從小到大排序為例，它的過程是先將待排序的數(shù)組構(gòu)建成一個大頂堆，此時，根結(jié)點就是最大值，將它放置在數(shù)組的結(jié)尾，然后將剩余數(shù)據(jù)重新構(gòu)建成一個堆，如此循環(huán)進(jìn)行，直到全部有序。

那，我們?nèi)绾螛?gòu)建一個大頂堆，又如何進(jìn)行調(diào)整呢？接下來，我們用一個數(shù)組示例，來演示堆排序的過程，假如數(shù)組如下：{50, 20, 90, 30, 80, 40, 70, 60, 10}，我們第一步要做的就是把它看做是一個完全二叉樹層序遍歷的結(jié)果集，所以它對應(yīng)的完全二叉樹如下：

完全二叉樹

我們要做的，就是把這棵完全二叉樹調(diào)整為一個大頂堆結(jié)構(gòu)，按照樹的一般處理思路，我們只需要把每個子樹都調(diào)整為大頂堆，就可以把整棵樹調(diào)整為大頂堆，所以，我們只需要自下而上，依次把分別以3、2、1、0為根結(jié)點的子樹調(diào)整為大頂堆即可，結(jié)點3就是最后一個子樹，之后的結(jié)點都是葉子結(jié)點。

下面先看調(diào)整的代碼，如下所示：

/**
 * 堆的調(diào)整
 * root：子樹的根結(jié)點位置
 * len：當(dāng)前排序數(shù)組的長度
 */
private void heapAdjust(int[] arr, int root, int len){
    if(len<=0)return;
    int temp;
    // 根結(jié)點的值先保存
    temp = arr[root];
    // i是這個結(jié)點的左孩子，或者是它孩子的左孩子
    for (int i=2*root+1; i<len; i=2*i+1) {
        if(i<len-1 && arr[i]<arr[i+1]){
            // 尋找到兩個孩子的較大者
            i++;
        }
        // 根結(jié)點的值比兩個孩子都大，就不需要再調(diào)整了
        if(temp>=arr[i]){
            break;
        }
        // 把根結(jié)點的值記為這個較大的孩子的值
        arr[root] = arr[i];
        // 再向下一級子樹遍歷
        root=i;
    }
    // 最后把temp的值存放在空置的位置
    arr[root] = temp;
}

按照以上思路，這段代碼看起來就比較簡單了，那就是尋找到這棵樹的最大值，并且每次都選擇它的兩個孩子中較大的那個進(jìn)行交換，最終最大值處于根結(jié)點。有了調(diào)整的代碼，我們就可以把原數(shù)組構(gòu)建成一個大頂堆了，只需要對結(jié)點3、2、1、0依次調(diào)用調(diào)整方法即可。如下所示：

for (int i = (len-2)/2; i>=0; i--) {
    heapAdjust(arr,i,len);
}

這里要說明一下 i 的起點的設(shè)置，按照我們的定義，一個長度為 n 的數(shù)組，其下標(biāo)范圍是 0 到(n-1)，如果 n 是奇數(shù)，那么最后一個有孩子的結(jié)點一定有兩個孩子，如上面這棵樹的結(jié)點3就有兩個孩子，如果 n 是偶數(shù)，那么最后一個有孩子的結(jié)點只有一個左孩子。對于有兩個孩子的，我們用n-1-1，就得到了它左孩子的下標(biāo)，對于只有一個孩子的，因為 n 是偶數(shù)，所以n-1是奇數(shù)，n-1-1還是偶數(shù)，可以知道(n-1)/2和(n-2)/2是相等的。綜上所述，我們使用(n-2)/2，就可以得到最后一個有孩子結(jié)點的下標(biāo)。

現(xiàn)在，就可以實現(xiàn)完整的堆排序算法了，只需要每次都把最大值移動到數(shù)組最后，然后剩余部分再進(jìn)行一次調(diào)整即可，代碼如下所示：

private static void heapSort(int[] arr){
    int len = arr.length;

    // 從最后一個有孩子的結(jié)點開始，逐一進(jìn)行堆的調(diào)整
    for (int i = (len-2)/2; i>=0; i--) {
        heapAdjust(arr,i,len);
    }


    // 對于一個堆，最大值一定在根結(jié)點，也就是在數(shù)組位置0，把它換到數(shù)組最后，然后對剩余的數(shù)據(jù)再進(jìn)行一次堆的調(diào)整
    for (int i = len-1; i>0; i--) {
        // 把最大值放在數(shù)組的最后
        swap(arr,0,i);

        // 剩余的值進(jìn)行堆的調(diào)整
        heapAdjust(arr,0,i);
    }
}

堆排序的最壞時間復(fù)雜度為O(nlogn)，其中 n 是外層循環(huán)，logn是調(diào)整內(nèi)部的for循環(huán)，這個for循環(huán)和遞歸類似。因為它對原始數(shù)據(jù)并不敏感，所以最好、平均和最壞時間復(fù)雜度都是O(nlogn)，和O(n2)相比效率高了很多。堆排序因為操作是在原地進(jìn)行，所以空間復(fù)雜度為O(1)。

歸并排序

歸并排序也利用了完全二叉樹，從而把時間復(fù)雜度降低到O(nlogn)，它的思想是一種分而治之的思想，我們這里以2路歸并排序為例，來說明它的核心原理。

假設(shè)初始序列含有 n 個記錄，則可以看成是 n 個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為 2 或 1 的有序子序列；再兩兩歸并，...，如此重復(fù)，直至得到一個長度為 n 的有序序列為止，這種排序方法稱為2路歸并排序。

歸并排序的原理并不復(fù)雜，通過一張圖就可以完全理解它的意圖，如下所示，它的過程就是先分后治的分而治之思想的體現(xiàn)：

歸并排序

分，就是把數(shù)組拆分成一條一條數(shù)據(jù)，2路歸并就是采用二分法，直到每部分只含一條數(shù)據(jù)為止。治，就是把數(shù)據(jù)排序后再合并，從而使得每部分有序，再合并，直到全部有序為止。分的過程可以使用遞歸，這很好實現(xiàn)，代碼如下所示：

private void mergeSort(int[] arr, int left, int right){
    if(left<right){
        int mid = (left+right)/2;
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        // 歸并操作
        ...
    }
}

接下來就是治的過程，這個過程就是把兩個有序數(shù)組合并成一個有序數(shù)組，以把{2, 8}和{3, 7}合并成{2, 3, 7, 8}為例，首先比較2和3，選擇2，如下所示：

選擇2

接下來應(yīng)該比較3和8，選擇3，如下所示：

選擇3

接下來比較7和8，選擇7之后，只剩下8了，可以肯定8及之后（如果有）的所有數(shù)據(jù)都是比較大且有序的，無需再次比較。根據(jù)這個思路，參考代碼如下所示：

private void merge(int[] arr, int[] temp, int left, int mid, int right){
    int i = left;
    int j = mid+1;
    int k = 0;
    while(i<=mid && j<=right){
        if(arr[i]<arr[j]){
            temp[k++] = arr[i++];
        }else{
            temp[k++] = arr[j++];
        }
    }

    while(i<=mid){
        temp[k++] = arr[i++];
    }
    while(j<=right){
        temp[k++] = arr[j++];
    }

    k=0;
    while (left<=right) {
        arr[left++] = temp[k++];
    }
}

其中temp是事先創(chuàng)建好的數(shù)組，因為數(shù)組的特殊性，比較操作無法在原數(shù)組進(jìn)行，所以需要在temp數(shù)組進(jìn)行比較后，再將有序結(jié)果復(fù)制到原數(shù)組。最終，歸并排序代碼如下：

private void mergeSort(int[] arr){
    int[] temp = new int[arr.length];
    mergeSort(arr,temp,0,arr.length-1);
}

private void mergeSort(int[] arr, int[] temp, int left, int right){
    if(left<right){
        int mid = (left+right)/2;
        mergeSort(arr,temp,left,mid);
        mergeSort(arr,temp,mid+1,right);
        merge(arr,temp,left,mid,right);
    }
}

歸并排序的時間復(fù)雜度是O(nlogn)，而以上使用遞歸的做法，它的空間復(fù)雜度是O(n+logn)，其中 n 是temp數(shù)組，logn是遞歸占用的?？臻g?？梢钥吹剑f歸占用了不菲的空間，那么我們能不能用非遞歸的方式實現(xiàn)歸并排序呢？答案是肯定的，許多遞歸都可以轉(zhuǎn)為線性操作。歸并排序是從單個數(shù)據(jù)開始的，而數(shù)組本身就可以看做是一個一個數(shù)據(jù)，非遞歸實現(xiàn)的思路如下：

非遞歸歸并排序

其中不同顏色代表不同的子數(shù)組，第一次從原數(shù)組進(jìn)行一次歸并后，temp數(shù)組中存放的其實就是第二次歸并的原始數(shù)據(jù)，這時只要再從temp數(shù)組歸并到原數(shù)組，就得到了第三次歸并的原始數(shù)據(jù)，重復(fù)下去，直到歸并完畢?？梢钥吹剑恍枰粋€數(shù)組的空間就可以完成全部過程，所以空間復(fù)雜度降低到了O(n)。因為篇幅的原因，代碼在文末github鏈接中，大家可以參考。

快速排序

快速排序：通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序的目的。

從這段定義可以發(fā)現(xiàn)，這又是遞歸可以發(fā)揮能力的算法，快速排序的關(guān)鍵在于用來分割的關(guān)鍵字的選擇。我們先從選擇每個子數(shù)組最左側(cè)數(shù)據(jù)為例來實現(xiàn)快速排序，代碼如下：

private void quickSort(int[] arr){
    qSort(arr,0,arr.length-1);
}

private void qSort(int[] arr, int low, int high) {
    int pivot;
    if(low<high){
        pivot = partition(arr,low,high);
        qSort(arr,low,pivot-1);
        qSort(arr,pivot+1,high);
    }
}

private int partition(int[] arr, int low, int high) {
    int pivotKey = arr[low];
    while (low<high) {
        while (low<high&&arr[high]>=pivotKey) {
            high--;
        }
        swap(arr,low,high);
        while (low<high&&arr[low]<=pivotKey) {
            low++;
        }
        swap(arr,low,high);
    }
    return low;
}

關(guān)鍵的代碼就在partition這個方法中，先選擇一個關(guān)鍵字，然后用它左右兩側(cè)數(shù)據(jù)與之對比并調(diào)整位置，最后返回這個關(guān)鍵字的地址，再以此分為左右兩部分重復(fù)此操作。下面，我們用一個簡單的數(shù)組來模擬以上操作，如下所示，紅色標(biāo)注的數(shù)據(jù)就是選擇的關(guān)鍵字：

快速排序

先比較high的值與關(guān)鍵字，如果不需要調(diào)整，就向前移動，如下所示：

high前移

接下來5和6都比關(guān)鍵字大，直到high的值為1時，交換low與high的值，注意我們的關(guān)鍵字還是2，如下所示：

交換low和high

接下來比較low的值與關(guān)鍵字，1比2小，所以low指針后移，如下所示：

low后移

接下來8比2大，所以交換low和high的值，如下所示：

交換low和high

接下來直到high指向 7 都不再進(jìn)行交換，第一輪排序就結(jié)束了，可以看到，low的值依然是之前的關(guān)鍵字。這也是為何先比較high指針再比較low指針的原因，也是為何最終返回low的原因。接下來只要按照這個規(guī)則，就可以把數(shù)組排序好。

快速排序最好的時間復(fù)雜度為O(nlogn)，也就是每次關(guān)鍵字取值都能恰好把數(shù)組平分兩部分時的情況，最壞時間復(fù)雜度是O(n2)，也就是十分不幸地，每次拆分都分成了一邊空一邊是剩余全部的兩部分。而空間復(fù)雜度也跟隨著變化，從O(logn)到O(n)。

可以看到，快速排序嚴(yán)重受關(guān)鍵字選擇的影響，像以上示例關(guān)鍵字2僅把數(shù)組分成了一邊長度為1、一邊長度為6的兩部分，顯然不夠高效。于是就有了三數(shù)取中法，做法是取三個關(guān)鍵字先進(jìn)行排序，然后用中間的值作為選擇的關(guān)鍵字，這樣的好處是這個關(guān)鍵字至少不是最大值或最小值，而且很有可能取到比較接近中間的值，這在大多數(shù)情況下都能提高一定的效率。三數(shù)取中法只需要在partition中增加以下代碼即可：

private static int partition(int[] arr, int low, int high) {
    // 三數(shù)取中法,把中間值存放在low中
    int mid = low + (high-low)/2;
    if (arr[low]>arr[high]) {
        swap(arr, low, high);
    }
    if (arr[mid]>arr[high]) {
        swap(arr,mid,high);
    }
    if (arr[low]>arr[mid]) {
        swap(arr,low,mid);
    }

    int pivotKey = arr[low];
    ...
}

當(dāng)然，三數(shù)取中法并不完美，它有可能很高效也可能很低效，這點就需要根據(jù)實際情況來合理選擇了，甚至有人提出采用九數(shù)取中法來進(jìn)一步提高效率，感興趣的話可以查閱相關(guān)資料進(jìn)一步研究。接下來我們對快速排序的其他部分進(jìn)行優(yōu)化，在排序過程中，選取的關(guān)鍵字從最初到最終的位置經(jīng)過了多次移動，這是沒有必要的，可以讓它直接到達(dá)終點，修改代碼如下所示：

private int partition(int[] arr, int low, int high) {
    int pivotKey = arr[low];

    // 暫存關(guān)鍵字
    int temp = pivotKey;

    while (low<high) {
        while (low<high&&arr[high]>=pivotKey) {
            high--;
        }
        arr[low] = arr[high];
        //swap(arr,low,high);
        while (low<high&&arr[low]<=pivotKey) {
            low++;
        }
        arr[high] = arr[low];
        // swap(arr,low,high);
    }
    // 恢復(fù)關(guān)鍵字
    arr[low] = temp;
    return low;
}

以上優(yōu)化用復(fù)制數(shù)據(jù)代替了交換數(shù)據(jù)，從而使性能有一定的提升，可以這樣做的原因是因為每次進(jìn)行交換的值都包含關(guān)鍵字。除此之外，它的遞歸部分也可以進(jìn)行優(yōu)化，優(yōu)化后的代碼如下所示：

private void qSort(int[] arr, int low, int high) {
    int pivot;
    // 遞歸
    // if(low<high){
    //     pivot = partition(arr,low,high);
    //     qSort(arr,low,pivot-1);
    //     qSort(arr,pivot+1,high);
    // }
    // 迭代代替遞歸
    while(low<high){
        pivot = partition(arr,low,high);
        qSort(arr,low,pivot-1);
        low = pivot+1;
    }
}

這個優(yōu)化就是用循環(huán)代替了遞歸，只是寫法上有些不同，是否真的有優(yōu)化效果還有待考證。關(guān)于遞歸和循環(huán)，也不一定是所有遞歸都應(yīng)該使用循環(huán)代替，這里有一篇文章我覺得分析的不錯，大家可以參考一下，鏈接如下：快速排序的優(yōu)化和關(guān)于遞歸的問題，說說我的想法。

分配排序

最后，我們還要講一個應(yīng)用場景較少的排序算法，它的時間復(fù)雜度可以達(dá)到線性階，也就是O(n)。根據(jù)不同的分配方式，又主要有計數(shù)排序、桶排序和基數(shù)排序三個算法。

1. 計數(shù)排序

計數(shù)排序的原理很簡單，顧名思義就是對每個數(shù)據(jù)計數(shù)，然后分配到下標(biāo)為0-max的數(shù)組中，然后對計數(shù)進(jìn)行排列即可。如下所示，桶中存儲的是每個數(shù)據(jù)出現(xiàn)的次數(shù)：

計數(shù)

有了計數(shù)，就可以得到排好序的數(shù)組了，0有0個，1有1個，所以第一個有序值是1，2有一個，所以第二個值是2，依次類推，最后有序數(shù)組為{1, 2, 3, 3, 5, 7, 7, 8}。實現(xiàn)代碼如下：

private void countingSort(int[] arr){
    int len = arr.length;
    // 獲取最大值
    int max = arr[0];
    for (int i = 1; i < len; i++) {
        if(max<arr[i]){
            max = arr[i];
        }
    }
    // 創(chuàng)建max+1個桶，從0-max
    int[] bucket = new int[max+1];
    for (int i = 0; i < len; i++) {
        // 每獲取一個數(shù)，就把它放在編號和其一致的桶中
        bucket[arr[i]]++;
    }
    int j = 0;
    for (int i = 0, bLen = bucket.length; i < bLen; i++) {
        // 遍歷桶，按順序恢復(fù)每條數(shù)據(jù)
        for (int k = bucket[i]; k > 0; k--) {
            arr[j++] = i;
        }
    }
}

因為一般重復(fù)數(shù)據(jù)比較少，所以每個桶內(nèi)的值不會很大，它的最好時間復(fù)雜度是O(n)。但是它有很嚴(yán)格的使用條件，那就是值是離散的，有窮的，而且數(shù)據(jù)要緊密，比如有數(shù)組{0, 2, 5, ..., 10000}，其中10000與其他數(shù)據(jù)差距很大，那么就會造成嚴(yán)重的空間浪費，也給遍歷增加了難度。但是如果數(shù)據(jù)能滿足這些要求，它的排序速度非?？臁?/p>

2. 桶排序

桶排序和計數(shù)排序類似，只是不再精確地一個下標(biāo)對應(yīng)一個數(shù)組，而是取多個區(qū)間，比如[0, 10), [10, 20), ...，然后每個部分再使用如直接插入排序等方法進(jìn)行排序。這一點和哈希表類似，需要數(shù)組和鏈表結(jié)合使用，如下所示：

桶排序

數(shù)組的每一位存儲的都是鏈表，對這個鏈表進(jìn)行排序比對全部數(shù)據(jù)排序要好的多，這里就不再給出代碼實現(xiàn)了。

3. 基數(shù)排序

基數(shù)排序，就是從每個數(shù)的低位開始排序，先排序個位數(shù)，再排序十位數(shù)、百位數(shù)，直至整個數(shù)組有序。它的原理如下所示，首先按照個位排序：

個位桶排序

根據(jù)個位排序的結(jié)果，再進(jìn)行十位數(shù)排序，如下所示：

十位桶排序

最后再按照百位數(shù)排序，如下所示：

百位桶排序

4. 總結(jié)

分配排序針對整數(shù)這種結(jié)構(gòu)，在數(shù)據(jù)較為均勻，緊密性較好的前提下進(jìn)行了優(yōu)化，可以使得排序時間復(fù)雜度接近O(n)。不過因為它的使用場景較少，且占用空間比較多，因此不常被使用。

總結(jié)

除了分配排序這種十分苛刻的排序算法，其他排序的時間復(fù)雜度都在O(nlogn)到O(n2)之間?？焖倥判蚴钱?dāng)前使用最多的一種排序算法，但是我們也不能盲目的選擇它，而是要針對實際情況選擇不同的算法。通常，當(dāng)數(shù)據(jù)量十分小（一般是7-10個）時，會使用直接插入排序來代替其它排序，因為當(dāng)數(shù)據(jù)很少時，算法的時間復(fù)雜度并不能作為評判算法效率的唯一標(biāo)準(zhǔn)，時間復(fù)雜度本身比較粗略，在 n 很小時有可能O(n2)比O(n)還要快，比如n=5，O(n2)算法實際運行次數(shù)是n2=25次，而O(n)算法實際運行次數(shù)是10n=50次，這時候常數(shù)項也會對算法有所影響。

最后，我們對多種排序的綜合性能進(jìn)行對比，如下表所示：

排序方法 最好情況 平均情況 最壞情況 輔助空間 穩(wěn)定性
冒泡排序 O(n) O(n2) O(n2) O(1) 穩(wěn)定
簡單選擇排序 O(n2) O(n2) O(n2) O(1) 穩(wěn)定
直接插入排序 O(n) O(n2) O(n2) O(1) 穩(wěn)定
希爾排序 O(n1.3) O(nlogn)-O(n2) O(n2) O(1) 不穩(wěn)定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不穩(wěn)定
歸并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 穩(wěn)定
快速排序 O(nlogn) O(nlogn) O(n2) O(logn)-O(n) 不穩(wěn)定
分配排序 O(n) O(n) O(n) O(n) 穩(wěn)定

最后，再對這里的穩(wěn)定性簡單說明一下，對于兩兩比較的算法一定是穩(wěn)定的，而存在跳躍比較的算法則是不穩(wěn)定的，因為兩兩比較的是相鄰值，那么相等的數(shù)據(jù)不會發(fā)生交換，而跳躍比較就無法保證了，所以如果對穩(wěn)定性要求很高，可能歸并排序就是最好的選擇。

以上就是常見排序算法的全部解析了，經(jīng)歷了這么多年，還誕生了更多更有趣的排序算法，以后有機(jī)會再來一睹為快吧。

以上涉及代碼均已上傳至我的github。

我是飛機(jī)醬，如果您喜歡我的文章，可以關(guān)注我~

編程之路，道阻且長。唯，路漫漫其修遠(yuǎn)兮，吾將上下而求索。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 一. 寫在前面 要學(xué)習(xí)算法，“排序”是一個回避不了的重要話題，在分析完并查集算法和常用數(shù)據(jù)結(jié)構(gòu)之后，今天我們終于可...
    Leesper閱讀 2,636評論 0贊 40
  • 排序的基本概念 在計算機(jī)程序開發(fā)過程中，經(jīng)常需要一組數(shù)據(jù)元素(或記錄)按某個關(guān)鍵字進(jìn)行排序，排序完成的序列可用于快...
    Jack921閱讀 1,565評論 1贊 4
  • 今天在朋友圈看到了這樣一段話：在電影《師父》中有一句臺詞——我不知道為什么每天要揮刀5000下，但是我知道這500...
    錦瑟_db50閱讀 302評論 0贊 0
  • 首先推薦大家使用小程序保存視頻，簡單快捷又方便 點擊查看小程序保存教程 如果小程序無法下載，可按照以下教程進(jìn)行下載...
    愛存圖閱讀 272,398評論 4贊 15
  • 不久前，《羋月傳》熱播之前，我寫了一篇科普《羋月傳》背景的文章，表明《羋月傳》的背景要比《甄嬛傳》宏大。那時候我還...
    王維鈞閱讀 932評論 4贊 5

友情鏈接更多精彩內(nèi)容