06堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

1 算法描述

• 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

  2 动图演示

  

  3 代码实现

  ```go func main() { nums := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3} fmt.Println(nums) HeapSort(nums) fmt.Println(nums) } func HeapSort(arr []int) { // 排序数组长度 length := len(arr) // 从0开始到length-1 for i:=0;i<length;i++ {
  //没有排序数组的长度

  unsortlen := length -i   
  // 求出非叶子节点的最大索引 
  leafnode := unsortlen/2 -1    

// 从最后一个非叶子节点的索引开始进行堆的构建 for j:=leafnode;j>=0;j— {
HeapBuild(arr,j,unsortlen)
} // 把堆顶元素和最后一个元素交换 arr[0],arr[unsortlen-1] = arr[unsortlen-1],arr[0]
} }

func HeapBuild(arr []int,i,length int) { // 根据i的值，可以知道左子树和右子树的索引值 left := 2 i +1
right := 2 i +2 // 左子树 大于 根节点值， 则交换，交换后，对左子树进行堆构建 if left < length && arr[left] > arr[i] { arr[i],arr[left] = arr[left],arr[i] HeapBuild(arr,left,length) } // 右子树大于根节点的值，则交换，交换后，对右子树进行堆构建 if right < length && arr[right] > arr[i] { arr[i],arr[right] = arr[right],arr[i] HeapBuild(arr,right,length) } } ```