设为首页 加入收藏

TOP

golang 堆排序
2019-05-28 18:07:57 】 浏览:23
Tags:golang 排序

堆排序的思想  因为堆的形式是完全二叉树,跟数组的索引形成映射,可以使用数组保存。先构建最大(小)堆,根结点就是最大(小)值,删除根结点之后的节点重新构建堆,依此顺序,即可完成堆排序。

代码实现

package main

import "fmt"

func main() {
   a := []int{34, 52, 12, 45, 56, 10, 35}
//fmt.Println(a[:len(a)])
HeapSort2(a)
}

func HeapSort2(a []int) {
   length := len(a)
for i:=0; i<length; i++ {
      BuildHeap(a[:length-i])
      a[0], a[length-i-1] = a[length-i-1], a[0]
      fmt.Println(i, a)
   }
}

func BuildHeap(a []int) {
   pos := len(a)
   start := (pos-2)/2
for i:=start; i>=0; i-- {
      AdjustHeap(a, i)
   }
}

//调整最大堆
func AdjustHeap(a []int, pos int) {
   length := len(a)
   current := pos
for current < length{
var child int
if 2*current+2 < length{
//有左右节点
if a[2*current+2] >= a[2*current+1] {
            child = 2*current+2
} else {
            child = 2*current+1
}
      } else if 

2*current+1 < length {
//只有左节点
child = 2*current+1
} else {
break;
      }

if a[current] < a[child] {
         a[current], a[child] = a[child], a[current]
         current = child
      } else {
break;
      }
   }
}

 


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇go语言的碎片整理:time 下一篇xorm-删除和软删除实例

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }