堆排序

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

堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

  • 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列.
  • 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列.

算法原理

堆排序的算法原理:

  • 创建一个堆 H[0……n-1].
  • 把堆首（最大值）和堆尾互换.
  • 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置.
  • 重复步骤2，直到堆的尺寸为 1.

    堆排序 - 图1

堆排序算法实现:

  1. func main()  {
  2.     array := []int{52,16,37,2,3,32,12,27,19,42,29,13,37,12,9}
  3.     HeapSort(array)
  4.     fmt.Println("HeapSort:",array)
  5. }
  7. func HeapSort(array []int) {
  8.     m := len(array)
  9.     s := m/2
  10.     for i := s; i > -1; i-- {
  11.         heap(array, i, m-1)
  12.     }
  13.     for i := m-1; i > 0; i-- {
  14.         array[i], array[0] = array[0], array[i]
  15.         heap(array, 0, i-1)
  16.     }
  17. }
  19. func heap(array []int, i, end int){
  20.     l := 2*i+1
  21.     if l > end {
  22.         return
  23.     }
  24.     n := l
  25.     r := 2*i+2
  26.     if r <= end && array[r]>array[l]{
  27.         n = r
  28.     }
  29.     if array[i] > array[n]{
  30.         return
  31.     }
  32.     array[n], array[i] = array[i], array[n]
  33.     heap(array, n, end)
  34. }

运行结果:

  1. HeapSort: [2 3 9 12 12 13 16 19 27 29 32 37 37 42 52]