[golang] 數據結構-堆排序

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

流程

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

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

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

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

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

復雜度
平均o(n*logn)
由于初次構建大根堆時有較多次的排序，所以不適合對少量元素進行排序。由于相同數值的節(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)二叉樹的數(qie)組(pian)表示，然后需要將這個亂序的樹調整為大根堆的狀態(tài)
    // 由于是從樹的右下角第一個非葉子節(jié)點開始從右向左從下往上進行比較，所以可以知道是從n/2-1這個位置的節(jié)點開始算
    for i := length/2 - 1; i >= 0; i-- {
        nodeSort(tree, i, length-1)
    }

    // 次數tree已經是個大根堆了。只需每次交換根節(jié)點和最后一個節(jié)點，并減少一個比較范圍。再進行一輪比較
    for i := length - 1; i > 0; i-- {
        // 如果只剩根節(jié)點和左孩子節(jié)點，就可以提前結束了
        if i == 1 && tree[0] <= tree[i] {
            break
        }
        // 交換根節(jié)點和比較范圍內最后一個節(jié)點的數值
        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é)點數值已經最大了，就不用再比下去了
    if tree[largerChild] <= tree[startNode] {
        return
    }

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

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

運行結果