Go语言用堆排序的方法进行一千万个int随机数排序.

上篇文章用的是quicksort方法排序,可是假设用高速排序法对反复率非常高的slice排序的时候,时间复杂度会激增,速度相当慢
所以尝试了一下堆排序,实验结果,感觉挺好的.以下是代码,大家能够參考一下,这个是建立的大顶堆.
二叉树的特性:
    最后一个非叶子节点 ： root = length/2(当length为奇数的时候root向下取整) 在GO语言中的索引位置：root - 1,
    左右孩子节点:child_l = 2*root,索引位置:child_l-1,右孩子的节点: 2*root+1 索引位置.

package main

import (
        "fmt"
        "math/rand"
)

func main() {
        Num := 10000000
        var list []int
        for i := Num; i > 0; i-- {
                list = append(list, rand.Intn(10000))
        }   //生成一千万个0---10000的随机数.
        length := len(list)
        for root := length/2 - 1; root >= 0; root-- {
                sort(list, root, length)
        } //第一次建立大顶堆
        for i := length - 1; i >= 1; i-- {
                list[0], list[i] = list[i], list[0]
                sort(list, 0, i)
        }  //调整位置并建并从第一个root開始建堆.假设不明确为什么,大家多把图画几遍就应该明朗了
        fmt.Println(list)
}
func sort(list []int, root, length int) {
        for {
                child := 2*root + 1 
                if child >= length {
                        break
                }   
                if child+1 < length && list[child] < list[child+1] {
                        child++ //这里重点讲一下,就是调整堆的时候,以左右孩子为节点的堆可能也须要调整
                }
                if list[root] > list[child] {
                        return
                }
                list[root], list[child] = list[child], list[root]
                root = child
        }
}