golang实现十大经典算法:堆排序

堆排序要点是运用堆的特点:最大堆前一半都是父节点

堆排序的优点:已有最大堆,排序会快

func main(){
 a := []int{0,1,2,4,5,6,7,8,9,10}//注意0是开头,必定存在
 heapSort(a,len(a)-1)
}
func shiftDown(a[]int,n int,i int){//下沉
	for i*2<=n{
		i = i*2
		if i+1<=n&&a[i+1]>a[i]{
			i+=1
		}
		if a[i/2]<a[i]{
			a[i],a[i/2] = a[i/2],a[i]
		}else{
			break
		}
	}
}

func makeHeap(a []int ,n int){//建立最大堆
	for i:=n/2;i>0;i--{
		shiftDown(a,n,i)
	}
}
func heapSort(a[]int,n int){//堆排序
	makeHeap(a,n)
	fmt.Println(a)//此时拥有最大堆性质,a[1]是根节点也是最大值
	for i:=n;i>0;i--{
		a[i],a[1] = a[1],a[i]//根最后一个非叶子节点交换,此时,10有序了
		shiftDown(a,i-1,1)
	}
}