摘要：希爾排序希爾排序這個名字，來源于它的發(fā)明者希爾，也稱作縮小增量排序，是插入排序的一種更高效的改進版本。我們可以發(fā)現(xiàn)，當(dāng)區(qū)間為的時候，它使用的排序方式就是插入排序。

冒泡排序無疑是最為出名的排序算法之一，從序列的一端開始往另一端冒泡（你可以從左往右冒泡，也可以從右往左冒泡，看心情），依次比較相鄰的兩個數(shù)的大?。ǖ降资潜却筮€是比小也看你心情）。

以 [ 8，2，5，9，7 ] 這組數(shù)字來做示例，上圖來戰(zhàn)：

從左往右依次冒泡，將小的往右移動

首先比較第一個數(shù)和第二個數(shù)的大小，我們發(fā)現(xiàn) 2 比 8 要小，那么保持原位，不做改動。位置還是 8，2，5，9，7 。

指針往右移動一格，接著比較：

比較第二個數(shù)和第三個數(shù)的大小，發(fā)現(xiàn) 2 比 5 要小，所以位置交換，交換后數(shù)組更新為：[ 8，5，2，9，7 ]。

指針再往右移動一格，繼續(xù)比較：

比較第三個數(shù)和第四個數(shù)的大小，發(fā)現(xiàn) 2 比 9 要小，所以位置交換，交換后數(shù)組更新為：[ 8，5，9，2，7 ]

同樣，指針再往右移動，繼續(xù)比較：

比較第 4 個數(shù)和第 5 個數(shù)的大小，發(fā)現(xiàn) 2 比 7 要小，所以位置交換，交換后數(shù)組更新為：[ 8，5，9，7，2 ]

下一步，指針再往右移動，發(fā)現(xiàn)已經(jīng)到底了，則本輪冒泡結(jié)束，處于最右邊的 2 就是已經(jīng)排好序的數(shù)字。

通過這一輪不斷的對比交換，數(shù)組中最小的數(shù)字移動到了最右邊。

接下來繼續(xù)第二輪冒泡：

由于右邊的 2 已經(jīng)是排好序的數(shù)字，就不再參與比較，所以本輪冒泡結(jié)束，本輪冒泡最終冒到頂部的數(shù)字 5 也歸于有序序列中，現(xiàn)在數(shù)組已經(jīng)變化成了[ 8，9，7，5，2 ]。

讓我們開始第三輪冒泡吧！

由于 8 比 7 大，所以位置不變，此時第三輪冒泡也已經(jīng)結(jié)束，第三輪冒泡的最后結(jié)果是[ 9，8，7，5，2 ]

緊接著第四輪冒泡：

9 和 8 比，位置不變，即確定了 8 進入有序序列，那么最后只剩下一個數(shù)字 9 ，放在末尾，自此排序結(jié)束。

public static void sort(int arr[]){
    for( int i = 0 ; i < arr.length - 1 ; i++ ){
        for(int j = 0;j < arr.length - 1 - i ; j++){
            int temp = 0;
            if(arr[j] < arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

冒泡的代碼還是相當(dāng)簡單的，兩層循環(huán)，外層冒泡輪數(shù)，里層依次比較，江湖中人人盡皆知。

我們看到嵌套循環(huán)，應(yīng)該立馬就可以得出這個算法的時間復(fù)雜度為O(n²)。

冒泡有一個最大的問題就是這種算法不管不管你有序還是沒序，閉著眼睛把你循環(huán)比較了再說。

比如我舉個數(shù)組例子：[ 9，8，7，6，5 ]，一個有序的數(shù)組，根本不需要排序，它仍然是雙層循環(huán)一個不少的把數(shù)據(jù)遍歷干凈，這其實就是做了沒必要做的事情，屬于浪費資源。

針對這個問題，我們可以設(shè)定一個臨時遍歷來標(biāo)記該數(shù)組是否已經(jīng)有序，如果有序了就不用遍歷了。

public static void sort(int arr[]){
    for( int i = 0;i < arr.length - 1 ; i++ ){
        boolean isSort = true;
        for( int j = 0;j < arr.length - 1 - i ; j++ ){
            int temp = 0;
            if(arr[j] < arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSort = false;
            }
        }
        if(isSort){
            break;
        }
    }
}

選擇排序的思路是這樣的：首先，找到數(shù)組中最小的元素，拎出來，將它和數(shù)組的第一個元素交換位置，第二步，在剩下的元素中繼續(xù)尋找最小的元素，拎出來，和數(shù)組的第二個元素交換位置，如此循環(huán)，直到整個數(shù)組排序完成。

至于選大還是選小，這個都無所謂，你也可以每次選擇最大的拎出來排，也可以每次選擇最小的拎出來的排，只要你的排序的手段是這種方式，都叫選擇排序。

我們還是以[ 8，2，5，9，7 ]這組數(shù)字做例子。

第一次選擇，先找到數(shù)組中最小的數(shù)字 2 ，然后和第一個數(shù)字交換位置。（如果第一個數(shù)字就是最小值，那么自己和自己交換位置，也可以不做處理，就是一個 if 的事情）

第二次選擇，由于數(shù)組第一個位置已經(jīng)是有序的，所以只需要查找剩余位置，找到其中最小的數(shù)字5，然后和數(shù)組第二個位置的元素交換。

第三次選擇，找到最小值 7 ，和第三個位置的元素交換位置。

第四次選擇，找到最小值8，和第四個位置的元素交換位置。

最后一個到達了數(shù)組末尾，沒有可對比的元素，結(jié)束選擇。

如此整個數(shù)組就排序完成了。

public static void sort(int arr[]){
    for( int i = 0;i < arr.length ; i++ ){
        int min = i;//最小元素的下標(biāo)
        for(int j = i + 1;j < arr.length ; j++ ){
            if(arr[j] < arr[min]){
                min = j;//找最小值
            }
        }
        //交換位置
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

雙層循環(huán)，時間復(fù)雜度和冒泡一模一樣，都是O(n²)

插入排序的思想和我們打撲克摸牌的時候一樣，從牌堆里一張一張摸起來的牌都是亂序的，我們會把摸起來的牌插入到左手中合適的位置，讓左手中的牌時刻保持一個有序的狀態(tài)。

那如果我們不是從牌堆里摸牌，而是左手里面初始化就是一堆亂牌呢？ 一樣的道理，我們把牌往手的右邊挪一挪，把手的左邊空出一點位置來，然后在亂牌中抽一張出來，插入到左邊，再抽一張出來，插入到左邊，再抽一張，插入到左邊，每次插入都插入到左邊合適的位置，時刻保持左邊的牌是有序的，直到右邊的牌抽完，則排序完畢。

數(shù)組初始化：[ 8，2，5，9，7 ]，我們把數(shù)組中的數(shù)據(jù)分成兩個區(qū)域，已排序區(qū)域和未排序區(qū)域，初始化的時候所有的數(shù)據(jù)都處在未排序區(qū)域中，已排序區(qū)域是空。

第一輪，從未排序區(qū)域中隨機拿出一個數(shù)字，既然是隨機，那么我們就獲取第一個，然后插入到已排序區(qū)域中，已排序區(qū)域是空，那么就不做比較，默認自身已經(jīng)是有序的了。（當(dāng)然了，第一輪在代碼中是可以省略的，從下標(biāo)為1的元素開始即可）

第二輪，繼續(xù)從未排序區(qū)域中拿出一個數(shù)，插入到已排序區(qū)域中，這個時候要遍歷已排序區(qū)域中的數(shù)字挨個做比較，比大比小取決于你是想升序排還是想倒序排，這里排升序：

第三輪，排 5 ：

第四輪，排 9 ：

第五輪，排 7

排序結(jié)束。

public static void sort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
        int value = arr[i];
        int j = 0;//插入的位置
        for (j = i-1; j >= 0; j--) {
            if (arr[j] > value) {
                arr[j+1] = arr[j];//移動數(shù)據(jù)
            } else {
                break;
            }
        }
        arr[j+1] = value; //插入數(shù)據(jù)
    }
}

從代碼里我們可以看出，如果找到了合適的位置，就不會再進行比較了，就好比牌堆里抽出的一張牌本身就比我手里的牌都小，那么我只需要直接放在末尾就行了，不用一個一個去移動數(shù)據(jù)騰出位置插入到中間。

所以說，最好情況的時間復(fù)雜度是 O(n)，最壞情況的時間復(fù)雜度是 O(n²)，然而時間復(fù)雜度這個指標(biāo)看的是最壞的情況，而不是最好的情況，所以插入排序的時間復(fù)雜度是 O(n²)。

希爾排序這個名字，來源于它的發(fā)明者希爾，也稱作“縮小增量排序”，是插入排序的一種更高效的改進版本。

我們知道，插入排序?qū)τ诖笠?guī)模的亂序數(shù)組的時候效率是比較慢的，因為它每次只能將數(shù)據(jù)移動一位，希爾排序為了加快插入的速度，讓數(shù)據(jù)移動的時候可以實現(xiàn)跳躍移動，節(jié)省了一部分的時間開支。

待排序數(shù)組 10 個數(shù)據(jù)：

假設(shè)計算出的排序區(qū)間為 4 ，那么我們第一次比較應(yīng)該是用第 5 個數(shù)據(jù)與第 1 個數(shù)據(jù)相比較。

調(diào)換后的數(shù)據(jù)為[ 7，2，5，9，8，10，1，15，12，3 ]，然后指針右移，第 6 個數(shù)據(jù)與第 2 個數(shù)據(jù)相比較。

指針右移，繼續(xù)比較。

如果交換數(shù)據(jù)后，發(fā)現(xiàn)減去區(qū)間得到的位置還存在數(shù)據(jù)，那么繼續(xù)比較，比如下面這張圖，12 和 8 相比較，原地不動后，指針從 12 跳到 8 身上，繼續(xù)減去區(qū)間發(fā)現(xiàn)前面還有一個下標(biāo)為 0 的數(shù)據(jù) 7 ，那么 8 和 7 相比較。

比較完之后的效果是 7，8，12 三個數(shù)為有序排列。

當(dāng)最后一個元素比較完之后，我們會發(fā)現(xiàn)大部分值比較大的數(shù)據(jù)都似乎調(diào)整到數(shù)組的中后部分了。

假設(shè)整個數(shù)組比較長的話，比如有 100 個數(shù)據(jù)，那么我們的區(qū)間肯定是四五十，調(diào)整后區(qū)間再縮小成一二十還會重新調(diào)整一輪，直到最后區(qū)間縮小為 1，就是真正的排序來了。

指針右移，繼續(xù)比較：

重復(fù)步驟，即可完成排序，重復(fù)的圖就不多畫了。

我們可以發(fā)現(xiàn)，當(dāng)區(qū)間為 1 的時候，它使用的排序方式就是插入排序。

public static void sort(int[] arr) {
    int length = arr.length;
    //區(qū)間
    int gap = 1;
    while (gap < length) {
        gap = gap * 3 + 1;
    }
    while (gap > 0) {
        for (int i = gap; i < length; i++) {
            int tmp = arr[i];
            int j = i - gap;
            //跨區(qū)間排序
            while (j >= 0 && arr[j] > tmp) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = tmp;
        }
        gap = gap / 3;
    }
}

可能你會問為什么區(qū)間要以 gap = gap*3 + 1 去計算，其實最優(yōu)的區(qū)間計算方法是沒有答案的，這是一個長期未解決的問題，不過差不多都會取在二分之一到三分之一附近。

歸并字面上的意思是合并，歸并算法的核心思想是分治法，就是將一個數(shù)組一刀切兩半，遞歸切，直到切成單個元素，然后重新組裝合并，單個元素合并成小數(shù)組，兩個小數(shù)組合并成大數(shù)組，直到最終合并完成，排序完畢。

我們以[ 8，2，5，9，7 ]這組數(shù)字來舉例

首先，一刀切兩半：

再切：

再切

粒度切到最小的時候，就開始歸并

數(shù)據(jù)量設(shè)定的比較少，是為了方便圖解，數(shù)據(jù)量為單數(shù)，是為了讓你看到細節(jié)，下面我畫了一張更直觀的圖可能你會更喜歡：

我們上面講過，歸并排序的核心思想是分治，分而治之，將一個大問題分解成無數(shù)的小問題進行處理，處理之后再合并，這里我們采用遞歸來實現(xiàn)：

    public static void sort(int[] arr) {
        int[] tempArr = new int[arr.length];
        sort(arr， tempArr， 0， arr.length-1);
    }

    /**
     * 歸并排序
     * @param arr 排序數(shù)組
     * @param tempArr 臨時存儲數(shù)組
     * @param startIndex 排序起始位置
     * @param endIndex 排序終止位置
     */
    private static void sort(int[] arr，int[] tempArr，int startIndex，int endIndex){
        if(endIndex <= startIndex){
            return;
        }
        //中部下標(biāo)
        int middleIndex = startIndex + (endIndex - startIndex) / 2;

        //分解
        sort(arr，tempArr，startIndex，middleIndex);
        sort(arr，tempArr，middleIndex + 1，endIndex);

        //歸并
        merge(arr，tempArr，startIndex，middleIndex，endIndex);
    }

    /**
     * 歸并
     * @param arr 排序數(shù)組
     * @param tempArr 臨時存儲數(shù)組
     * @param startIndex 歸并起始位置
     * @param middleIndex 歸并中間位置
     * @param endIndex 歸并終止位置
     */
    private static void merge(int[] arr， int[] tempArr， int startIndex， int middleIndex， int endIndex) {
        //復(fù)制要合并的數(shù)據(jù)
        for (int s = startIndex; s <= endIndex; s++) {
            tempArr[s] = arr[s];
        }

        int left = startIndex;//左邊首位下標(biāo)
        int right = middleIndex + 1;//右邊首位下標(biāo)
        for (int k = startIndex; k <= endIndex; k++) {
            if(left > middleIndex){
                //如果左邊的首位下標(biāo)大于中部下標(biāo)，證明左邊的數(shù)據(jù)已經(jīng)排完了。
                arr[k] = tempArr[right++];
            } else if (right > endIndex){
                //如果右邊的首位下標(biāo)大于了數(shù)組長度，證明右邊的數(shù)據(jù)已經(jīng)排完了。
                arr[k] = tempArr[left++];
            } else if (tempArr[right] < tempArr[left]){
                arr[k] = tempArr[right++];//將右邊的首位排入，然后右邊的下標(biāo)指針+1。
            } else {
                arr[k] = tempArr[left++];//將左邊的首位排入，然后左邊的下標(biāo)指針+1。
            }
        }
    }

我們可以發(fā)現(xiàn) merge 方法中只有一個 for 循環(huán)，直接就可以得出每次合并的時間復(fù)雜度為 O(n) ，而分解數(shù)組每次對半切割，屬于對數(shù)時間 O(log n) ，合起來等于 O(log2n) ，也就是說，總的時間復(fù)雜度為 O(nlogn) 。

關(guān)于空間復(fù)雜度，其實大部分人寫的歸并都是在 merge 方法里面申請臨時數(shù)組，用臨時數(shù)組來輔助排序工作，空間復(fù)雜度為 O(n)，而我這里做的是原地歸并，只在最開始申請了一個臨時數(shù)組，所以空間復(fù)雜度為 O(1)。

快速排序的核心思想也是分治法，分而治之。它的實現(xiàn)方式是每次從序列中選出一個基準值，其他數(shù)依次和基準值做比較，比基準值大的放右邊，比基準值小的放左邊，然后再對左邊和右邊的兩組數(shù)分別選出一個基準值，進行同樣的比較移動，重復(fù)步驟，直到最后都變成單個元素，整個數(shù)組就成了有序的序列。

我們以[ 8，2，5，0，7，4，6，1 ]這組數(shù)字來進行演示

首先，我們隨機選擇一個基準值：

與其他元素依次比較，大的放右邊，小的放左邊：

然后我們以同樣的方式排左邊的數(shù)據(jù)：

繼續(xù)排 0 和 1 ：

由于只剩下一個數(shù)，所以就不用排了，現(xiàn)在的數(shù)組序列是下圖這個樣子：

右邊以同樣的操作進行，即可排序完成。

快速排序的關(guān)鍵之處在于切分，切分的同時要進行比較和移動，這里介紹一種叫做單邊掃描的做法。

我們隨意抽取一個數(shù)作為基準值，同時設(shè)定一個標(biāo)記 mark 代表左邊序列最右側(cè)的下標(biāo)位置，當(dāng)然初始為 0 ，接下來遍歷數(shù)組，如果元素大于基準值，無操作，繼續(xù)遍歷，如果元素小于基準值，則把 mark + 1 ，再將 mark 所在位置的元素和遍歷到的元素交換位置，mark 這個位置存儲的是比基準值小的數(shù)據(jù)，當(dāng)遍歷結(jié)束后，將基準值與 mark 所在元素交換位置即可。

public static void sort(int[] arr) {
    sort(arr， 0， arr.length - 1);
}

private static void sort(int[] arr， int startIndex， int endIndex) {
    if (endIndex <= startIndex) {
        return;
    }
    //切分
    int pivotIndex = partitionV2(arr， startIndex， endIndex);
    sort(arr， startIndex， pivotIndex-1);
    sort(arr， pivotIndex+1， endIndex);
}

private static int partition(int[] arr， int startIndex， int endIndex) {
    int pivot = arr[startIndex];//取基準值
    int mark = startIndex;//Mark初始化為起始下標(biāo)

    for(int i=startIndex+1; i<=endIndex; i++){
        if(arr[i]
雙邊掃描
另外還有一種雙邊掃描的做法，看起來比較直觀：我們隨意抽取一個數(shù)作為基準值，然后從數(shù)組左右兩邊進行掃描，先從左往右找到一個大于基準值的元素，將下標(biāo)指針記錄下來，然后轉(zhuǎn)到從右往左掃描，找到一個小于基準值的元素，交換這兩個元素的位置，重復(fù)步驟，直到左右兩個指針相遇，再將基準值與左側(cè)最右邊的元素交換。
我們來看一下實現(xiàn)代碼，不同之處只有 partition 方法：
public static void sort(int[] arr) {
    sort(arr， 0， arr.length - 1);
}

private static void sort(int[] arr， int startIndex， int endIndex) {
    if (endIndex <= startIndex) {
        return;
    }
    //切分
    int pivotIndex = partition(arr， startIndex， endIndex);
    sort(arr， startIndex， pivotIndex-1);
    sort(arr， pivotIndex+1， endIndex);
}


private static int partition(int[] arr， int startIndex， int endIndex) {
    int left = startIndex;
    int right = endIndex;
    int pivot = arr[startIndex];//取第一個元素為基準值

    while (true) {
        //從左往右掃描
        while (arr[left] <= pivot) {
            left++;
            if (left == right) {
                break;
            }
        }

        //從右往左掃描
        while (pivot < arr[right]) {
            right--;
            if (left == right) {
                break;
            }
        }

        //左右指針相遇
        if (left >= right) {
            break;
        }

        //交換左右數(shù)據(jù)
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

    //將基準值插入序列
    int temp = arr[startIndex];
    arr[startIndex] = arr[right];
    arr[right] = temp;
    return right;
}
極端情況
快速排序的時間復(fù)雜度和歸并排序一樣，O(n log n)，但這是建立在每次切分都能把數(shù)組一刀切兩半差不多大的前提下，如果出現(xiàn)極端情況，比如排一個有序的序列，如[ 9，8，7，6，5，4，3，2，1 ]，選取基準值 9 ，那么需要切分 n - 1 次才能完成整個快速排序的過程，這種情況下，時間復(fù)雜度就退化成了 O(n2)，當(dāng)然極端情況出現(xiàn)的概率也是比較低的。
所以說，快速排序的時間復(fù)雜度是 O(nlogn)，極端情況下會退化成 O(n2)，為了避免極端情況的發(fā)生，選取基準值應(yīng)該做到隨機選取，或者是打亂一下數(shù)組再選取。
另外，快速排序的空間復(fù)雜度為 O(1)。
堆排序
堆排序顧名思義，是利用堆這種數(shù)據(jù)結(jié)構(gòu)來進行排序的算法。
如果你不了解堆這種數(shù)據(jù)結(jié)構(gòu)，可以查看小吳之前的數(shù)據(jù)結(jié)構(gòu)系列文章---看動畫輕松理解堆 
如果你了解堆這種數(shù)據(jù)結(jié)構(gòu)，你應(yīng)該知道堆是一種優(yōu)先隊列，兩種實現(xiàn)，最大堆和最小堆，由于我們這里排序按升序排，所以就直接以最大堆來說吧。
我們完全可以把堆（以下全都默認為最大堆）看成一棵完全二叉樹，但是位于堆頂?shù)脑乜偸钦脴涞淖畲笾?，每個子節(jié)點的值都比父節(jié)點小，由于堆要時刻保持這樣的規(guī)則特性，所以一旦堆里面的數(shù)據(jù)發(fā)生變化，我們必須對堆重新進行一次構(gòu)建。
既然堆頂元素永遠都是整棵樹中的最大值，那么我們將數(shù)據(jù)構(gòu)建成堆后，只需要從堆頂取元素不就好了嗎？ 第一次取的元素，是否取的就是最大值？取完后把堆重新構(gòu)建一下，然后再取堆頂?shù)脑兀欠袢〉木褪堑诙蟮闹担?反復(fù)的取，取出來的數(shù)據(jù)也就是有序的數(shù)據(jù)。

圖解堆排
我們以[ 8，2，5，9，7，3 ]這組數(shù)據(jù)來演示。
首先，將數(shù)組構(gòu)建成堆。

既然構(gòu)建成堆結(jié)構(gòu)了，那么接下來，我們?nèi)〕龆秧數(shù)臄?shù)據(jù)，也就是數(shù)組第一個數(shù) 9 ，取法是將數(shù)組的第一位和最后一位調(diào)換，然后將數(shù)組的待排序范圍 -1。

現(xiàn)在的待排序數(shù)據(jù)是[ 3，8，5，2，7 ]，我們繼續(xù)將待排序數(shù)據(jù)構(gòu)建成堆。

取出堆頂數(shù)據(jù)，這次就是第一位和倒數(shù)第二位交換了，因為待排序的邊界已經(jīng)減 1 。

繼續(xù)構(gòu)建堆

從堆頂取出來的數(shù)據(jù)最終形成一個有序列表，重復(fù)的步驟就不再贅述了，我們來看一下代碼實現(xiàn)。
代碼實現(xiàn)
public static void sort(int[] arr) {
    int length = arr.length;
    //構(gòu)建堆
    buildHeap(arr， length);
    for ( int i = length - 1; i > 0; i-- ) {
        //將堆頂元素與末位元素調(diào)換
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        //數(shù)組長度-1 隱藏堆尾元素
        length--;
        //將堆頂元素下沉 目的是將最大的元素浮到堆頂來
        sink(arr， 0， length);
    }
}
private static void buildHeap(int[] arr， int length) {
    for (int i = length / 2; i >= 0; i--) {
        sink(arr， i， length);
    }
}

/**
 * 下沉調(diào)整
 * @param arr 數(shù)組
 * @param index 調(diào)整位置
 * @param length 數(shù)組范圍
 */
private static void sink(int[] arr， int index， int length) {
    int leftChild = 2 * index + 1;//左子節(jié)點下標(biāo)
    int rightChild = 2 * index + 2;//右子節(jié)點下標(biāo)
    int present = index;//要調(diào)整的節(jié)點下標(biāo)

    //下沉左邊
    if (leftChild < length && arr[leftChild] > arr[present]) {
        present = leftChild;
    }

    //下沉右邊
    if (rightChild < length && arr[rightChild] > arr[present]) {
        present = rightChild;
    }

    //如果下標(biāo)不相等 證明調(diào)換過了
    if (present != index) {
        //交換值
        int temp = arr[index];
        arr[index] = arr[present];
        arr[present] = temp;

        //繼續(xù)下沉
        sink(arr， present， length);
    }
}


堆排序和快速排序的時間復(fù)雜度都一樣是 O(nlogn)。
計數(shù)排序
計數(shù)排序是一種非基于比較的排序算法，我們之前介紹的各種排序算法幾乎都是基于元素之間的比較來進行排序的，計數(shù)排序的時間復(fù)雜度為 O(n + m )，m 指的是數(shù)據(jù)量，說的簡單點，計數(shù)排序算法的時間復(fù)雜度約等于 O(n)，快于任何比較型的排序算法。

圖解計數(shù)
以下以[ 3，5，8，2，5，4 ]這組數(shù)字來演示。
首先，我們找到這組數(shù)字中最大的數(shù)，也就是 8，創(chuàng)建一個最大下標(biāo)為 8 的空數(shù)組 arr 。

遍歷數(shù)據(jù)，將數(shù)據(jù)的出現(xiàn)次數(shù)填入arr中對應(yīng)的下標(biāo)位置中。

遍歷 arr ，將數(shù)據(jù)依次取出即可。

代碼實現(xiàn)
public static void sort(int[] arr) {
    //找出數(shù)組中的最大值
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    //初始化計數(shù)數(shù)組
    int[] countArr = new int[max + 1];

    //計數(shù)
    for (int i = 0; i < arr.length; i++) {
        countArr[arr[i]]++;
        arr[i] = 0;
    }
    
    //排序
    int index = 0;
    for (int i = 0; i < countArr.length; i++) {
        if (countArr[i] > 0) {
            arr[index++] = i;
        }
    }
}


穩(wěn)定排序
有一個需求就是當(dāng)對成績進行排名次的時候，如何在原來排前面的人，排序后還是處于相同成績的人的前面。
解題的思路是對 countArr 計數(shù)數(shù)組進行一個變形，變來和名次掛鉤，我們知道 countArr 存放的是分數(shù)的出現(xiàn)次數(shù)，那么其實我們可以算出每個分數(shù)的最大名次，就是將 countArr 中的每個元素順序求和。
如下圖：

變形之后是什么意思呢？
我們把原數(shù)組[ 2，5，8，2，5，4 ]中的數(shù)據(jù)依次拿來去 countArr 去找，你會發(fā)現(xiàn) 3 這個數(shù)在 countArr[3] 中的值是 2 ，代表著排名第二名，（因為第一名是最小的 2，對吧？），5 這個數(shù)在 countArr[5] 中的值是 5 ，為什么是 5 呢？我們來數(shù)數(shù)，排序后的數(shù)組應(yīng)該是[ 2，3，4，5，5，8 ]，5 的排名是第五名，那 4 的排名是第幾名呢？對應(yīng) countArr[4] 的值是 3 ，第三名，5 的排名是第五名是因為 5 這個數(shù)有兩個，自然占據(jù)了第 4 名和第 5 名。
所以我們?nèi)∨琶臅r候應(yīng)該特別注意，原數(shù)組中的數(shù)據(jù)要從右往左取，從 countArr 取出排名后要把 countArr 中的排名減 1 ，以便于再次取重復(fù)數(shù)據(jù)的時候排名往前一位。
對應(yīng)代碼實現(xiàn)：
public static void sort(int[] arr) {
    //找出數(shù)組中的最大值
    int max = arr[0];
    for (int i = 1; i < arr.length; ++i) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    //初始化計數(shù)數(shù)組
    int[] countArr = new int[max + 1];

    //計數(shù)
    for (int i = 0; i < arr.length; ++i) {
        countArr[arr[i]]++;
    }

    //順序累加
    for (int i = 1; i < max + 1; ++i) {
        countArr[i] = countArr[i-1] + countArr[i];
    }

    //排序后的數(shù)組
    int[] sortedArr = new int[arr.length];
    
    //排序
    for (int i = arr.length - 1; i >= 0; --i) {
        sortedArr[countArr[arr[i]]-1] = arr[i];
        countArr[arr[i]]--;
    }

    //將排序后的數(shù)據(jù)拷貝到原數(shù)組
    for (int i = 0; i < arr.length; ++i) {
        arr[i] = sortedArr[i];
    }
}



計數(shù)局限性
計數(shù)排序的毛病很多，我們來找找 bug 。
如果我要排的數(shù)據(jù)里有 0 呢？ int[] 初始化內(nèi)容全是 0 ，排毛線。
如果我要排的數(shù)據(jù)范圍比較大呢？比如[ 1，9999 ]，我排兩個數(shù)你要創(chuàng)建一個 int[10000] 的數(shù)組來計數(shù)？
對于第一個 bug ，我們可以使用偏移量來解決，比如我要排[ -1，0，-3 ]這組數(shù)字，這個簡單，我全給你們加 10 來計數(shù)，變成[ 9，10，7 ]計完數(shù)后寫回原數(shù)組時再減 10。不過有可能也會踩到坑，萬一你數(shù)組里恰好有一個 -10，你加上 10 后又變 0 了，排毛線。
對于第二個 bug ，確實解決不了，如果是[ 9998，9999 ]這種雖然值大但是相差范圍不大的數(shù)據(jù)我們也可以使用偏移量解決，比如這兩個數(shù)據(jù)，我減掉 9997 后只需要申請一個 int[3] 的數(shù)組就可以進行計數(shù)。
由此可見，計數(shù)排序只適用于正整數(shù)并且取值范圍相差不大的數(shù)組排序使用，它的排序的速度是非?？捎^的。
桶排序
桶排序可以看成是計數(shù)排序的升級版，它將要排的數(shù)據(jù)分到多個有序的桶里，每個桶里的數(shù)據(jù)再多帶帶排序，再把每個桶的數(shù)據(jù)依次取出，即可完成排序。

圖解桶排序
我們拿一組計數(shù)排序啃不掉的數(shù)據(jù) [ 500，6123，1700，10，9999 ] 來舉例。
第一步，我們創(chuàng)建 10 個桶，分別來裝 0-1000 、1000-2000 、 2000-3000 、 3000-4000 、 4000-5000 、5000-6000、 6000-7000 、7000-8000 、8000-9000 區(qū)間的數(shù)據(jù)。

第二步，遍歷原數(shù)組，對號入桶。

第三步，對桶中的數(shù)據(jù)進行多帶帶排序，只有第一個桶中的數(shù)量大于 1 ，顯然只需要排第一個桶。

最后，依次將桶中的數(shù)據(jù)取出，排序完成。

代碼實現(xiàn)
這個桶排序乍一看好像挺簡單的，但是要敲代碼就需要考慮幾個問題了。
桶這個東西怎么表示？
怎么確定桶的數(shù)量？
桶內(nèi)排序用什么方法排？
代碼如下：
public static void sort(int[] arr){
    //最大最小值
    int max = arr[0];
    int min = arr[0];
    int length = arr.length;

    for(int i=1; i max) {
            max = arr[i];
        } else if(arr[i] < min) {
            min = arr[i];
        }
    }

    //最大值和最小值的差
    int diff = max - min;

    //桶列表
    ArrayList> bucketList = new ArrayList<>();
    for(int i = 0; i < length; i++){
        bucketList.add(new ArrayList<>());
    }

    //每個桶的存數(shù)區(qū)間
    float section = (float) diff / (float) (length - 1);

    //數(shù)據(jù)入桶
    for(int i = 0; i < length; i++){
        //當(dāng)前數(shù)除以區(qū)間得出存放桶的位置 減1后得出桶的下標(biāo)
        int num = (int) (arr[i] / section) - 1;
        if(num < 0){
            num = 0;
        }
        bucketList.get(num).add(arr[i]);
    }

    //桶內(nèi)排序
    for(int i = 0; i < bucketList.size(); i++){
        //jdk的排序速度當(dāng)然信得過
        Collections.sort(bucketList.get(i));
    }

    //寫入原數(shù)組
    int index = 0;
    for(ArrayList arrayList : bucketList){
        for(int value : arrayList){
            arr[index] = value;
            index++;
        }
    }
}


桶當(dāng)然是一個可以存放數(shù)據(jù)的集合，我這里使用 arrayList ，如果你使用 LinkedList 那其實也是沒有問題的。
桶的數(shù)量我認為設(shè)置為原數(shù)組的長度是合理的，因為理想情況下每個數(shù)據(jù)裝一個桶。
數(shù)據(jù)入桶的映射算法其實是一個開放性問題，我承認我這里寫的方案并不佳，因為我測試過不同的數(shù)據(jù)集合來排序，如果你有什么更好的方案或想法，歡迎留言討論。
桶內(nèi)排序為了方便起見使用了當(dāng)前語言提供的排序方法，如果對于穩(wěn)定排序有所要求，可以選擇使用自定義的排序算法。
桶排序的思考及其應(yīng)用
在額外空間充足的情況下，盡量增大桶的數(shù)量，極限情況下每個桶只有一個數(shù)據(jù)時，或者是每只桶只裝一個值時，完全避開了桶內(nèi)排序的操作，桶排序的最好時間復(fù)雜度就能夠達到 O(n)。
比如高考總分 750 分，全國幾百萬人，我們只需要創(chuàng)建 751 個桶，循環(huán)一遍挨個扔進去，排序速度是毫秒級。
但是如果數(shù)據(jù)經(jīng)過桶的劃分之后，桶與桶的數(shù)據(jù)分布極不均勻，有些數(shù)據(jù)非常多，有些數(shù)據(jù)非常少，比如[ 8，2，9，10，1，23，53，22，12，9000 ]這十個數(shù)據(jù)，我們分成十個桶裝，結(jié)果發(fā)現(xiàn)第一個桶裝了 9 個數(shù)據(jù)，這是非常影響效率的情況，會使時間復(fù)雜度下降到 O(nlogn)，解決辦法是我們每次桶內(nèi)排序時判斷一下數(shù)據(jù)量，如果桶里的數(shù)據(jù)量過大，那么應(yīng)該在桶里面回調(diào)自身再進行一次桶排序。
基數(shù)排序
基數(shù)排序是一種非比較型整數(shù)排序算法，其原理是將數(shù)據(jù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。
假設(shè)說，我們要對 100 萬個手機號碼進行排序，應(yīng)該選擇什么排序算法呢？排的快的有歸并、快排時間復(fù)雜度是 O(nlogn)，計數(shù)排序和桶排序雖然更快一些，但是手機號碼位數(shù)是11位，那得需要多少桶？內(nèi)存條表示不服。
這個時候，我們使用基數(shù)排序是最好的選擇。

圖解基排
我們以[ 892， 846， 821， 199， 810，700 ]這組數(shù)字來做例子演示。
首先，創(chuàng)建十個桶，用來輔助排序。

先排個位數(shù)，根據(jù)個位數(shù)的值將數(shù)據(jù)放到對應(yīng)下標(biāo)值的桶中。

排完后，我們將桶中的數(shù)據(jù)依次取出。

那么接下來，我們排十位數(shù)。

最后，排百位數(shù)。

排序完成。
代碼實現(xiàn)
基數(shù)排序可以看成桶排序的擴展，也是用桶來輔助排序，代碼如下：
public static void sort(int[] arr){
    int length = arr.length;

    //最大值
    int max = arr[0];
    for(int i = 0;i < length;i++){
        if(arr[i] > max){
            max = arr[i];
        }
    }
    //當(dāng)前排序位置
    int location = 1;

    //桶列表
    ArrayList> bucketList = new ArrayList<>();

    //長度為10 裝入余數(shù)0-9的數(shù)據(jù)
    for(int i = 0; i < 10; i++){
        bucketList.add(new ArrayList());
    }

    while(true)
    {
        //判斷是否排完
        int dd = (int)Math.pow(10，(location - 1));
        if(max < dd){
            break;
        }

        //數(shù)據(jù)入桶
        for(int i = 0; i < length; i++)
        {
            //計算余數(shù) 放入相應(yīng)的桶
            int number = ((arr[i] / dd) % 10);
            bucketList.get(number).add(arr[i]);
        }

        //寫回數(shù)組
        int nn = 0;
        for (int i=0;i<10;i++){
            int size = bucketList.get(i).size();
            for(int ii = 0;ii < size;ii ++){
                arr[nn++] = bucketList.get(i).get(ii);
            }
            bucketList.get(i).clear();
        }
        location++;
    }
}
其實它的思想很簡單，不管你的數(shù)字有多大，按照一位一位的排，0 - 9 最多也就十個桶：先按權(quán)重小的位置排序，然后按權(quán)重大的位置排序。
當(dāng)然，如果你有需求，也可以選擇從高位往低位排。
總結(jié)
感謝你看到了這里，希望看完這篇文章能讓你清晰的理解平時最常用的十大排序算法。
?? 看完三件事：
如果你覺得這篇內(nèi)容對你挺有啟發(fā)，我想邀請你幫我三個忙：

點贊，讓更多的人也能看到這篇內(nèi)容（收藏不點贊，都是耍流氓 -_-）
關(guān)注我和專欄，讓我們成為長期關(guān)系
關(guān)注公眾號「五分鐘學(xué)算法」，第一時間閱讀最新的算法文章，公眾號后臺回復(fù) 1024 送你 50 本 算法編程書籍。