算法代码实现之堆排序,Golang(Go语言)实现

QQ245671051 · · 2325 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

封装成函数:

//堆排序
//s[0]不用,实际元素从角标1开始
//父节点元素大于子节点元素
//左子节点角标为2*k
//右子节点角标为2*k+1
//父节点角标为k/2
func HeapSort(s []int) {
N := len(s) - 1 //s[0]不用,实际元素数量和最后一个元素的角标都为N
//构造堆
//如果给两个已构造好的堆添加一个共同父节点,
//将新添加的节点作一次下沉将构造一个新堆,
//由于叶子节点都可看作一个构造好的堆,所以
//可以从最后一个非叶子节点开始下沉,直至
//根节点,最后一个非叶子节点是最后一个叶子
//节点的父节点,角标为N/2
for k := N / 2; k >= 1; k-- {
sink(s, k, N)
}
//下沉排序
for N > 1 {
swap(s, 1, N) //将大的放在数组后面,升序排序
N--
sink(s, 1, N)
}
}
 
//下沉(由上至下的堆有序化)
func sink(s []int, k, N int) {
for {
i := 2 * k
if i > N { //保证该节点是非叶子节点
break
}
if i < N && s[i+1] > s[i] { //选择较大的子节点
i++
}
if s[k] >= s[i] { //没下沉到底就构造好堆了
break
}
swap(s, k, i)
k = i
}
}
 
func swap(s []int, i int, j int) {
s[i], s[j] = s[j], s[i]
}

测试:

s := []int{-1,9, 0, 6, 5, 8, 2, 1, 7, 4, 3}
fmt.Println(s[1:])
HeapSort(s)
fmt.Println(s[1:])

输出:

[9 0 6 5 8 2 1 7 4 3]
[0 1 2 3 4 5 6 7 8 9]


有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:QQ245671051

查看原文:算法代码实现之堆排序,Golang(Go语言)实现

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

2325 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传