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

冒泡排序無(wú)疑是最為出名的排序算法之一，從序列的一端開始往另一端冒泡（你可以從左往右冒泡，也可以從右往左冒泡，看心情），依次比較相鄰的兩個(gè)數(shù)的大小（到底是比大還是比小也看你心情）。

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

從左往右依次冒泡，將小的往右移動(dòng)

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

指針往右移動(dòng)一格，接著比較：

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

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

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

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

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

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

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

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

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

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

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

緊接著第四輪冒泡：

9 和 8 比，位置不變，即確定了 8 進(jìn)入有序序列，那么最后只剩下一個(gè)數(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)簡(jiǎn)單的，兩層循環(huán)，外層冒泡輪數(shù)，里層依次比較，江湖中人人盡皆知。

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

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

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

針對(duì)這個(gè)問(wèn)題，我們可以設(shè)定一個(gè)臨時(shí)遍歷來(lái)標(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ù)組中最小的元素，拎出來(lái)，將它和數(shù)組的第一個(gè)元素交換位置，第二步，在剩下的元素中繼續(xù)尋找最小的元素，拎出來(lái)，和數(shù)組的第二個(gè)元素交換位置，如此循環(huán)，直到整個(gè)數(shù)組排序完成。

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

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

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

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

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

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

最后一個(gè)到達(dá)了數(shù)組末尾，沒(méi)有可對(duì)比的元素，結(jié)束選擇。

如此整個(gè)數(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)，時(shí)間復(fù)雜度和冒泡一模一樣，都是O(n²)

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

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

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

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

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

第三輪，排 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];//移動(dòng)數(shù)據(jù)
            } else {
                break;
            }
        }
        arr[j+1] = value; //插入數(shù)據(jù)
    }
}

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

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

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

我們知道，插入排序?qū)τ诖笠?guī)模的亂序數(shù)組的時(shí)候效率是比較慢的，因?yàn)樗看沃荒軐?shù)據(jù)移動(dòng)一位，希爾排序?yàn)榱思涌觳迦氲乃俣?，讓?shù)據(jù)移動(dòng)的時(shí)候可以實(shí)現(xiàn)跳躍移動(dòng)，節(jié)省了一部分的時(shí)間開支。

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

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

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

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

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

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

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

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

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

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

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

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

可能你會(huì)問(wèn)為什么區(qū)間要以 gap = gap*3 + 1 去計(jì)算，其實(shí)最優(yōu)的區(qū)間計(jì)算方法是沒(méi)有答案的，這是一個(gè)長(zhǎng)期未解決的問(wèn)題，不過(guò)差不多都會(huì)取在二分之一到三分之一附近。

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

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

首先，一刀切兩半：

再切：

再切

粒度切到最小的時(shí)候，就開始?xì)w并

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

我們上面講過(guò)，歸并排序的核心思想是分治，分而治之，將一個(gè)大問(wèn)題分解成無(wú)數(shù)的小問(wèn)題進(jìn)行處理，處理之后再合并，這里我們采用遞歸來(lái)實(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í)存儲(chǔ)數(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í)存儲(chǔ)數(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ù)組長(zhǎng)度，證明右邊的數(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 方法中只有一個(gè) for 循環(huán)，直接就可以得出每次合并的時(shí)間復(fù)雜度為 O(n) ，而分解數(shù)組每次對(duì)半切割，屬于對(duì)數(shù)時(shí)間 O(log n) ，合起來(lái)等于 O(log2n) ，也就是說(shuō)，總的時(shí)間復(fù)雜度為 O(nlogn) 。

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

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

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

首先，我們隨機(jī)選擇一個(gè)基準(zhǔn)值：

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

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

繼續(xù)排 0 和 1 ：

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

右邊以同樣的操作進(jìn)行，即可排序完成。

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

我們隨意抽取一個(gè)數(shù)作為基準(zhǔn)值，同時(shí)設(shè)定一個(gè)標(biāo)記 mark 代表左邊序列最右側(cè)的下標(biāo)位置，當(dāng)然初始為 0 ，接下來(lái)遍歷數(shù)組，如果元素大于基準(zhǔn)值，無(wú)操作，繼續(xù)遍歷，如果元素小于基準(zhǔn)值，則把 mark + 1 ，再將 mark 所在位置的元素和遍歷到的元素交換位置，mark 這個(gè)位置存儲(chǔ)的是比基準(zhǔn)值小的數(shù)據(jù)，當(dāng)遍歷結(jié)束后，將基準(zhǔn)值與 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];//取基準(zhǔn)值
    int mark = startIndex;//Mark初始化為起始下標(biāo)

    for(int i=startIndex+1; i<=endIndex; i++){
        if(arr[i]
雙邊掃描
另外還有一種雙邊掃描的做法，看起來(lái)比較直觀：我們隨意抽取一個(gè)數(shù)作為基準(zhǔn)值，然后從數(shù)組左右兩邊進(jìn)行掃描，先從左往右找到一個(gè)大于基準(zhǔn)值的元素，將下標(biāo)指針記錄下來(lái)，然后轉(zhuǎn)到從右往左掃描，找到一個(gè)小于基準(zhǔn)值的元素，交換這兩個(gè)元素的位置，重復(fù)步驟，直到左右兩個(gè)指針相遇，再將基準(zhǔn)值與左側(cè)最右邊的元素交換。
我們來(lái)看一下實(shí)現(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];//取第一個(gè)元素為基準(zhǔn)值

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

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

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

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

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

取出堆頂數(shù)據(jù)，這次就是第一位和倒數(shù)第二位交換了，因?yàn)榇判虻倪吔缫呀?jīng)減 1 。

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

從堆頂取出來(lái)的數(shù)據(jù)最終形成一個(gè)有序列表，重復(fù)的步驟就不再贅述了，我們來(lái)看一下代碼實(shí)現(xiàn)。
代碼實(shí)現(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ù)組長(zhǎng)度-1 隱藏堆尾元素
        length--;
        //將堆頂元素下沉 目的是將最大的元素浮到堆頂來(lái)
        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é)點(diǎn)下標(biāo)
    int rightChild = 2 * index + 2;//右子節(jié)點(diǎn)下標(biāo)
    int present = index;//要調(diào)整的節(jié)點(diǎn)下標(biāo)

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

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

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

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


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

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

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

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

代碼實(shí)現(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];
        }
    }
    //初始化計(jì)數(shù)數(shù)組
    int[] countArr = new int[max + 1];

    //計(jì)數(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)定排序
有一個(gè)需求就是當(dāng)對(duì)成績(jī)進(jìn)行排名次的時(shí)候，如何在原來(lái)排前面的人，排序后還是處于相同成績(jī)的人的前面。
解題的思路是對(duì) countArr 計(jì)數(shù)數(shù)組進(jìn)行一個(gè)變形，變來(lái)和名次掛鉤，我們知道 countArr 存放的是分?jǐn)?shù)的出現(xiàn)次數(shù)，那么其實(shí)我們可以算出每個(gè)分?jǐn)?shù)的最大名次，就是將 countArr 中的每個(gè)元素順序求和。
如下圖：

變形之后是什么意思呢？
我們把原數(shù)組[ 2，5，8，2，5，4 ]中的數(shù)據(jù)依次拿來(lái)去 countArr 去找，你會(huì)發(fā)現(xiàn) 3 這個(gè)數(shù)在 countArr[3] 中的值是 2 ，代表著排名第二名，（因?yàn)榈谝幻亲钚〉?2，對(duì)吧？），5 這個(gè)數(shù)在 countArr[5] 中的值是 5 ，為什么是 5 呢？我們來(lái)數(shù)數(shù)，排序后的數(shù)組應(yīng)該是[ 2，3，4，5，5，8 ]，5 的排名是第五名，那 4 的排名是第幾名呢？對(duì)應(yīng) countArr[4] 的值是 3 ，第三名，5 的排名是第五名是因?yàn)?5 這個(gè)數(shù)有兩個(gè)，自然占據(jù)了第 4 名和第 5 名。
所以我們?nèi)∨琶臅r(shí)候應(yīng)該特別注意，原數(shù)組中的數(shù)據(jù)要從右往左取，從 countArr 取出排名后要把 countArr 中的排名減 1 ，以便于再次取重復(fù)數(shù)據(jù)的時(shí)候排名往前一位。
對(duì)應(yīng)代碼實(shí)現(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];
        }
    }

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

    //計(jì)數(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];
    }
}



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

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

第二步，遍歷原數(shù)組，對(duì)號(hào)入桶。

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

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

代碼實(shí)現(xiàn)
這個(gè)桶排序乍一看好像挺簡(jiǎn)單的，但是要敲代碼就需要考慮幾個(gè)問(wèn)題了。
桶這個(gè)東西怎么表示？
怎么確定桶的數(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<>());
    }

    //每個(gè)桶的存數(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)然信得過(guò)
        Collections.sort(bucketList.get(i));
    }

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


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

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

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

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

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

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

排序完成。
代碼實(shí)現(xiàn)
基數(shù)排序可以看成桶排序的擴(kuò)展，也是用桶來(lái)輔助排序，代碼如下：
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<>();

    //長(zhǎng)度為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++)
        {
            //計(jì)算余數(shù) 放入相應(yīng)的桶
            int number = ((arr[i] / dd) % 10);
            bucketList.get(number).add(arr[i]);
        }

        //寫回?cá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í)它的思想很簡(jiǎn)單，不管你的數(shù)字有多大，按照一位一位的排，0 - 9 最多也就十個(gè)桶：先按權(quán)重小的位置排序，然后按權(quán)重大的位置排序。
當(dāng)然，如果你有需求，也可以選擇從高位往低位排。
總結(jié)
感謝你看到了這里，希望看完這篇文章能讓你清晰的理解平時(shí)最常用的十大排序算法。
?? 看完三件事：
如果你覺(jué)得這篇內(nèi)容對(duì)你挺有啟發(fā)，我想邀請(qǐng)你幫我三個(gè)忙：

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