圖解堆排序，詳細(xì)！

寫(xiě)在前面：

大家好，我是時(shí)光。

今天給大家?guī)?lái)的是排序算法中的堆排序，這種排序跟二叉樹(shù)相關(guān)。我采用圖解方式講解，爭(zhēng)取寫(xiě)透徹。話不多說(shuō)，開(kāi)始！

思維導(dǎo)圖：

1，堆排序概念

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

相關(guān)概念：

1.1，二叉樹(shù)

特征：每個(gè)節(jié)點(diǎn)最多只有2個(gè)子節(jié)點(diǎn)（不存在度大于2的節(jié)點(diǎn)）

1.2，滿二叉樹(shù)

滿二叉樹(shù)：葉子節(jié)點(diǎn)全部都在最底層；除葉子節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)都有左右孩子；

1.3，完全二叉樹(shù)

完全二叉樹(shù)：葉子節(jié)點(diǎn)全部都在最底的兩層；最后一層只缺少右邊的葉子節(jié)點(diǎn)，左邊一定有葉子節(jié)點(diǎn)；除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)均達(dá)到最大值；

1.4，最大堆和最小堆

最大堆：堆頂是整個(gè)堆中最大元素

最小堆：堆頂是整個(gè)堆中最小元素

2，算法思路

我們先搞清楚這個(gè)堆排序思想，先把邏輯搞清楚，不著急寫(xiě)代碼。

我們首先有一個(gè)無(wú)序數(shù)組，比方說(shuō)

int[] arr={4,2,8,0,5,7,1,3,9};

既然用到堆，肯定先要將數(shù)組構(gòu)建成二叉堆。需要對(duì)數(shù)組從小到大排序，則構(gòu)建成最大堆；需要對(duì)數(shù)組從小到大排序，則構(gòu)建成最小堆。

2.1，第一個(gè)步驟，初始化堆

我們先來(lái)看看數(shù)組是如何存儲(chǔ)二叉樹(shù)的

注意：這里考慮的當(dāng)前節(jié)點(diǎn)，必須是完全二叉樹(shù)的非葉子節(jié)點(diǎn)。并且節(jié)點(diǎn)的左孩子和右孩子必須小于數(shù)組長(zhǎng)度，所以后面需要添加限制條件。

看到上圖中的公式，我們明白了數(shù)組是可以存儲(chǔ)完全二叉樹(shù)，同時(shí)保留節(jié)點(diǎn)之間的關(guān)系。以上述數(shù)組為例

那么存儲(chǔ)好之后，如何將二叉樹(shù)構(gòu)建成二叉堆呢？繼續(xù)往下看

以這個(gè)圖為例，我們以最大堆舉例，若要構(gòu)建二叉堆，則A要比B和C都大，B要比D和E都大，C要比F和G都大。也就是說(shuō)父節(jié)點(diǎn)要比子節(jié)點(diǎn)都大才行。

在這個(gè)圖中，明顯不滿足最大堆的要求。我們先拿序號(hào)為3,7,8的三個(gè)節(jié)點(diǎn)來(lái)研究，i=3的節(jié)點(diǎn)比i=7和i=8的節(jié)點(diǎn)都小，所以需要交換位置。注意此圖是從0開(kāi)始，也就是模擬數(shù)組下標(biāo)從0開(kāi)始。

怎么交換呢？很簡(jiǎn)單。我們看節(jié)點(diǎn)0，設(shè)為當(dāng)前節(jié)點(diǎn)index，那么它的lchild=index*2+1，它的rchild=index*2+2；注意下標(biāo)從0開(kāi)始。

//初始化堆
public static void HeapAdjust(int[] arr,int index,int len){
        //先保存當(dāng)前節(jié)點(diǎn)的下標(biāo)
        int max = index;
        //保存左右孩子數(shù)組下標(biāo)
        int lchild = index*2+1;
        int rchild = index*2+2;
        //開(kāi)始調(diào)整，左右孩子下標(biāo)必須小于len，也就是確保數(shù)組不會(huì)越界
        if(lchild<len && arr[lchild] > arr[max]){
            max=lchild;
        }
        if(rchild<len && arr[rchild] > arr[max]){
            max=rchild;
        }
        //若發(fā)生了交換，則max肯定不等于index了。此時(shí)max節(jié)點(diǎn)值需要與index節(jié)點(diǎn)值交換，上面交換索引值，這里交換節(jié)點(diǎn)值
        if(max!=index){
            int temp=arr[index];
            arr[index]=arr[max];
            arr[max]=temp;
            //交換完之后需要再次對(duì)max進(jìn)行調(diào)整，因?yàn)榇藭r(shí)max有可能不滿足最大堆
            HeapAdjust(arr,max,len);
        }
    }

上面代碼很好理解，中間的兩個(gè)if語(yǔ)句就是交換節(jié)點(diǎn)索引值，只要有一個(gè)孩子節(jié)點(diǎn)大于index，就需要進(jìn)行交換。若父節(jié)點(diǎn)index比兩個(gè)孩子節(jié)點(diǎn)都大，那么就不需要交換了。

最后面的if語(yǔ)句是交換節(jié)點(diǎn)值，我們知道，只要index與lchild和rchild有交換，則index一定不等于max了！

那為什么最后的if語(yǔ)句里面還要加上一個(gè)遞歸寫(xiě)法呢？我們舉個(gè)例子就明白了，還是以上述數(shù)組為例，先看看一輪交換之后的樣子：

第一次交換，0與9交換，此時(shí)Index=9；

第二次交換，8已經(jīng)比7和1都大了，此時(shí)不需要交換；

第三次交換，2與9交換，此時(shí)Index=9；

第四次交換，4與9交換，此時(shí)Index=9，第一輪交換到此結(jié)束。

一輪結(jié)束后，有小伙伴兒已經(jīng)發(fā)現(xiàn)問(wèn)題了，雖然9成功的成為最大堆的堆頂元素，但是下面的其他元素并不滿足最大堆的要求，比如說(shuō)左下角的元素2,元素3,元素0等這種二叉樹(shù)就不滿足，元素4，元素2，元素5也不滿足。

因此在交換節(jié)點(diǎn)值這個(gè)步驟里，我們需要進(jìn)行遞歸操作，交換完之后再次對(duì)index進(jìn)行堆調(diào)整：

//若發(fā)生了交換，則max肯定不等于index了。此時(shí)max節(jié)點(diǎn)值需要與index節(jié)點(diǎn)值交換，上面交換索引值，這里交換節(jié)點(diǎn)值
if(max!=index){
    int temp=arr[index];
    arr[index]=arr[max];
    arr[max]=temp;
    //交換完之后需要再次對(duì)max進(jìn)行調(diào)整，因?yàn)榇藭r(shí)max有可能不滿足最大堆
    HeapAdjust(arr,max,len);
}

堆排序的測(cè)試：

//堆排序
    public static int[] HeapSort(int[] arr){
        int len=arr.length;
        /**
         * 第一步，初始化堆，最大堆，從小到大
         * i從完全二叉樹(shù)的第一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，也就是len/2-1開(kāi)始(數(shù)組下標(biāo)從0開(kāi)始)
         */
        for(int i=len/2-1;i>=0;i--){
            HeapAdjust(arr,i,len);
        }
        //打印堆頂元素，應(yīng)該為最大元素9
        System.out.println(arr[0]);
        return arr;
    }

上述代碼就是從完全二叉樹(shù)的第一個(gè)非葉子節(jié)點(diǎn)開(kāi)始調(diào)換，還順便打印堆頂元素，此時(shí)應(yīng)為9；

至此，第一個(gè)步驟，初始化堆完成，最后的結(jié)果應(yīng)該為下圖：

2.2，第二個(gè)步驟，堆排序

堆排序的過(guò)程就是將堆頂元素（最大值或者最小值）與二叉堆的最末尾葉子節(jié)點(diǎn)進(jìn)行調(diào)換，不停的調(diào)換，直到二叉堆的順序變成從小到大或者從大到小，也就實(shí)現(xiàn)了我們的目的。

我們這里以最大堆的堆頂元素（最大元素）為例，最后調(diào)換的結(jié)果就是從小到大排序的結(jié)果。

第一次交換，我們直接將元素9與元素0交換，此時(shí)堆頂元素為0，設(shè)當(dāng)前節(jié)點(diǎn)index=0；

這時(shí)，我們需要將剩下的元素（排除元素9）進(jìn)行堆排序，直到下面這個(gè)結(jié)果：

代碼：

/**
 * 第二步，交換堆頂（最大）元素和二叉堆的最后一個(gè)葉子節(jié)點(diǎn)元素。目的是交換元素
 * i從二叉堆的最后一個(gè)葉子節(jié)點(diǎn)元素開(kāi)始，也就是len-1開(kāi)始(數(shù)組下標(biāo)從0開(kāi)始)
 */
for(int i=len-1;i>=0;i--){
    int temp=arr[i];
    arr[i]=arr[0];
    arr[0]=temp;
    //交換完之后需要重新調(diào)整二叉堆，從頭開(kāi)始調(diào)整，此時(shí)Index=0
    HeapAdjust(arr,0,i);
}

注意：這里有個(gè)小細(xì)節(jié)問(wèn)題，前面我們寫(xiě)的初始化堆方法有三個(gè)參數(shù)，分別是數(shù)組arr，當(dāng)前節(jié)點(diǎn)index以及數(shù)組長(zhǎng)度len，如下：

HeapAdjust(int[] arr,int index,int len)

那么，為何不直接傳入兩個(gè)參數(shù)即可，數(shù)組長(zhǎng)度直接用arr.length表示不就行了嗎？初始化堆的時(shí)候是可以，但是后面在交換堆頂元素和末尾的葉子節(jié)點(diǎn)時(shí)，在對(duì)剩下的元素進(jìn)行排序時(shí)，此時(shí)的數(shù)組長(zhǎng)度可不是arr.length了，應(yīng)該是變化的參數(shù)i，因?yàn)榻粨Q之后的元素（比如9）就不計(jì)入堆中排序了，所以需要3個(gè)參數(shù)。

我們進(jìn)行第二次交換，我們直接將元素8與元素2交換，此時(shí)堆頂元素為2，設(shè)當(dāng)前節(jié)點(diǎn)index=2；

這時(shí)，我們需要將剩下的元素（排除元素9和8）進(jìn)行堆排序，直到下面這個(gè)結(jié)果：

到這個(gè)時(shí)候，我們?cè)僦貜?fù)上述步驟，不斷調(diào)換堆頂和最末尾的節(jié)點(diǎn)元素即可，再不斷地對(duì)剩下的元素進(jìn)行排序，最后就能得到從小到大排序好的堆了，如下圖所示，這就是我們想要的結(jié)果：

3，完整代碼

import java.util.Arrays;

public class Head_Sort {
    public static void main(String[] args) {
        int[] arr={4,2,8,0,5,7,1,3,9};
        System.out.println("排序前:"+Arrays.toString(arr));
        System.out.println("排序后:"+Arrays.toString(HeapSort(arr)));
    }

    //堆排序
    public static int[] HeapSort(int[] arr){
        int len=arr.length;
        /**
         * 第一步，初始化堆，最大堆，從小到大。目的是對(duì)元素排序
         * i從完全二叉樹(shù)的第一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，也就是len/2-1開(kāi)始(數(shù)組下標(biāo)從0開(kāi)始)
         */
        for(int i=len/2-1;i>=0;i--){
            HeapAdjust(arr,i,len);
        }
        /**
         * 第二步，交換堆頂（最大）元素和二叉堆的最后一個(gè)葉子節(jié)點(diǎn)元素。目的是交換元素
         * i從二叉堆的最后一個(gè)葉子節(jié)點(diǎn)元素開(kāi)始，也就是len-1開(kāi)始(數(shù)組下標(biāo)從0開(kāi)始)
         */
        for(int i=len-1;i>=0;i--){
            int temp=arr[i];
            arr[i]=arr[0];
            arr[0]=temp;
            //交換完之后需要重新調(diào)整二叉堆，從頭開(kāi)始調(diào)整，此時(shí)Index=0
            HeapAdjust(arr,0,i);
        }
        return arr;
    }

    /**
     *初始化堆
     * @param arr 待調(diào)整的二叉樹(shù)(數(shù)組)
     * @param index 待調(diào)整的節(jié)點(diǎn)下標(biāo)，二叉樹(shù)的第一個(gè)非葉子節(jié)點(diǎn)
     * @param len 待調(diào)整的數(shù)組長(zhǎng)度
     */
    public static void HeapAdjust(int[] arr,int index,int len){
        //先保存當(dāng)前節(jié)點(diǎn)的下標(biāo)
        int max = index;
        //保存左右孩子數(shù)組下標(biāo)
        int lchild = index*2+1;
        int rchild = index*2+2;
        //開(kāi)始調(diào)整，左右孩子下標(biāo)必須小于len，也就是確保index必須是非葉子節(jié)點(diǎn)
        if(lchild<len && arr[lchild] > arr[max]){
            max=lchild;
        }
        if(rchild<len && arr[rchild] > arr[max]){
            max=rchild;
        }
        //若發(fā)生了交換，則max肯定不等于index了。此時(shí)max節(jié)點(diǎn)值需要與index節(jié)點(diǎn)值交換，上面交換索引值，這里交換節(jié)點(diǎn)值
        if(max!=index){
            int temp=arr[index];
            arr[index]=arr[max];
            arr[max]=temp;
            //交換完之后需要再次對(duì)max進(jìn)行調(diào)整，因?yàn)榇藭r(shí)max有可能不滿足最大堆
            HeapAdjust(arr,max,len);
        }
    }
}

運(yùn)行結(jié)果：

4，算法分析

4.1，時(shí)間復(fù)雜度

建堆的時(shí)候初始化堆過(guò)程(HeapAdjust)是堆排序的關(guān)鍵，時(shí)間復(fù)雜度為O(log n)，下面看堆排序的兩個(gè)過(guò)程；

第一步，初始化堆，這一步時(shí)間復(fù)雜度是O(n)；

第二步，交換堆頂元素過(guò)程，需要用到n-1次循環(huán)，且每一次都要用到(HeapAdjust)，所以時(shí)間復(fù)雜度為((n-1)*log n)~O(nlog n)；

最終時(shí)間復(fù)雜度：O(n)+O(nlog n)，后者復(fù)雜度高于前者，所以堆排序的時(shí)間復(fù)雜度為O(nlog n)；

4.2，空間復(fù)雜度

空間復(fù)雜度是O(1)，因?yàn)闆](méi)有用到額外開(kāi)辟的集合空間。

4.3，算法穩(wěn)定性

堆排序是不穩(wěn)定的，比方說(shuō)二叉樹(shù)[6a，8，13，6b]，（這里的6a和6b數(shù)值上都是6，只不過(guò)為了區(qū)別6所以這樣）經(jīng)過(guò)堆初始化后以及排序過(guò)后就變成[6b，6a，8，13]；可見(jiàn)堆排序是不穩(wěn)定的。