golang 堆排序

2024-05-22 13:03:08 97

堆排序

堆排序本身需要将数组看作一个完全二叉树，然后动态的将这棵树维护成一个大根堆或小根堆

code

packagemain

import"fmt"



funcmain(){

//要将数组看作一个完全二叉树

arrs:=[]int{3,2,7,5,9,1,7,8,4,6,5,7}

fmt.Printf("beforearris:%v\n",arrs)

heapSort(arrs)

fmt.Printf("afterarris:%v\n",arrs)

}



funcheapSort(arrs[]int){

l:=len(arrs)

initHeap(arrs,l)



//当前已经建立一个大根堆

//开始排序

fori:=l-1;i>0;i--{

//取出堆顶元素

arrs[0],arrs[i]=arrs[i],arrs[0]



//此时堆顶已经不再是最大的元素，需要对整个堆做一次sink

//待排序的堆是arrs[:l]

l--

sink(arrs,0,l)

}

}



//初始化一个堆

funcinitHeap(arrs[]int,lint){

fori:=l/2;i>=0;i--{

sink(arrs,i,l)

}

}

//sink可以生成一个以i为根节点的大根堆

funcsink(arrs[]int,i,lint){

//左右子孩子

left,right:=2*i+1,2*i+2



//largest用来记录i和两个子孩子中最大的那个

largest:=i



ifleft<l&&arrs[left]>arrs[largest]{

largest=left

}



ifright<l&&arrs[right]>arrs[largest]{

largest=right

}



iflargest!=i{

arrs[largest],arrs[i]=arrs[i],arrs[largest]

//此时arrs[i]已经是i,left,right三个里最大的了

//largest的值变化了，要从新sink以largest为root的堆

sink(arrs,largest,l)

}

}

结果

beforearris:[327591784657]

afterarris:[123455677789]

原文链接：

golang 堆排序

堆排序

code

结果

热门推荐

随机推荐