接上文 樹形選擇排序
上篇也說了，樹形選擇排序相較簡單選擇排序，雖然減少了時間復(fù)雜度，但是使用了較多空間去儲存每輪比較的結(jié)果，并且每次還要再和勝出節(jié)點比較。而堆排序就是為了優(yōu)化這個問題而在1964年被兩位大佬發(fā)明。

原理
首先有幾個關(guān)于樹的定義：

如果一棵樹每個節(jié)點的值都大于（小于）或等于其字節(jié)點的話，那么這棵樹就是大（?。└鶚?/strong>
如果一棵大（小）根樹正好又是完全二叉樹，則被稱為大根堆（小根堆）

堆排序就是利用大根堆（小根堆）的特性進(jìn)行排序的。
從小到大排序一般用大根堆，從大到小一般用小根堆。

流程

• 先把待排序的數(shù)組8、4、12、7、35、9、22、41、2用完全二叉樹表示
  

• 按大根堆的特性把這個完全二叉樹從最后一個非葉子節(jié)點開始比較，把較大值交換到當(dāng)前位置。遇到上層節(jié)點順序影響下層節(jié)點不滿足大根堆特性時，再對下層節(jié)點進(jìn)行排序。最終得到初始狀態(tài)的大根堆。
  
  

• 然后將根節(jié)點與最后一個葉子節(jié)點進(jìn)行交換
  

• 交換后，忽略最后一個葉子節(jié)點，再對這棵樹的節(jié)點進(jìn)行比較與交換，再次得到符合大根堆要求的樹。然后繼續(xù)將根節(jié)點與最后的葉子節(jié)點進(jìn)行交換
  

• 以此類推，最終可以得到一個有序的數(shù)組
  

復(fù)雜度
平均o(n*logn)
由于初次構(gòu)建大根堆時有較多次的排序，所以不適合對少量元素進(jìn)行排序。由于相同數(shù)值的節(jié)點在比較過程中不能保證順序，所以是種不穩(wěn)定的排序方法。

代碼

package main

import (
    "fmt"
    "math/rand"
)

func main() {
    var length = 20
    var tree []int

    for i := 0; i < length; i++ {
        tree = append(tree, int(rand.Intn(1000)))
    }
    fmt.Println(tree)

    // 此時的切片o可以理解為初始狀態(tài)二叉樹的數(shù)(qie)組(pian)表示，然后需要將這個亂序的樹調(diào)整為大根堆的狀態(tài)
    // 由于是從樹的右下角第一個非葉子節(jié)點開始從右向左從下往上進(jìn)行比較，所以可以知道是從n/2-1這個位置的節(jié)點開始算
    for i := length/2 - 1; i >= 0; i-- {
        nodeSort(tree, i, length-1)
    }

    // 次數(shù)tree已經(jīng)是個大根堆了。只需每次交換根節(jié)點和最后一個節(jié)點，并減少一個比較范圍。再進(jìn)行一輪比較
    for i := length - 1; i > 0; i-- {
        // 如果只剩根節(jié)點和左孩子節(jié)點，就可以提前結(jié)束了
        if i == 1 && tree[0] <= tree[i] {
            break
        }
        // 交換根節(jié)點和比較范圍內(nèi)最后一個節(jié)點的數(shù)值
        tree[0], tree[i] = tree[i], tree[0]
        // 這里遞歸的把較大值一層層提上來
        nodeSort(tree, 0, i -1)
        fmt.Println(tree)
    }
}

func nodeSort(tree []int, startNode, latestNode int) {
    var largerChild int
    leftChild := startNode*2 + 1
    rightChild := leftChild + 1

    // 子節(jié)點超過比較范圍就跳出遞歸
    if leftChild >= latestNode {
        return
    }

    // 左右孩子節(jié)點中找到較大的，右孩子不能超出比較的范圍
    if rightChild <= latestNode && tree[rightChild] > tree[leftChild] {
        largerChild = rightChild
    } else {
        largerChild = leftChild
    }

    // 此時startNode節(jié)點數(shù)值已經(jīng)大了，就不用再比下去了
    if tree[largerChild] <= tree[startNode] {
        return
    }

    // 到這里發(fā)現(xiàn)孩子節(jié)點數(shù)值比父節(jié)點大，所以交換位置，并繼續(xù)比較子孫節(jié)點，直到把大魚撈上來
    tree[startNode], tree[largerChild] = tree[largerChild], tree[startNode]
    nodeSort(tree, largerChild, latestNode)
}

注：代碼里用遞歸并不是最優(yōu)解

運行結(jié)果

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。