常见的排序算法-2.1 选择排序(堆排序)

选择排序的优化方案（堆排序）

package mysort

type HeapSort struct {
   Sort
   size int
}

// 对数据进行原地建堆
//将建立好的堆的root最后的位置交换位置，然后将size -- 然后将0号位置进行下滤操作
//siftdown 直到堆的值为1
// 选最值使用堆来操作
// 第一个叶子节点是size 的一半 所以第一个非叶子节点 是 (size >> 1) -1
func (this *HeapSort) SortFunc() {
   this.size = len(this.Array)
   for i := (this.size >> 1) - 1; i >= 0; i-- {
      this.siftDown(i)
   }
   for this.size > 1 {
      this.Swap(0, this.size-1)
      this.size--
      this.siftDown(0)
   }

}
func (this *HeapSort) siftDown(index int) {
   v := this.Array[index]
   half := (this.size >> 1)
   // 1.找其左右子节点 找到最大的子节点开始交换数值
   for index < half {
      // 1.index 只有左节点
      // index 有左右子节点
      //默认和左边进行比较
      childIndex := (index << 1) + 1
      childValue := this.Array[childIndex]
      rightIndex := childIndex + 1
      if rightIndex < this.size && this.Array[rightIndex] > childValue {
         childIndex = rightIndex
         childValue = this.Array[childIndex]
      }
      if v >= childValue {
         break
      }
      this.Array[index] = childValue
      index = childIndex

   }
   this.Array[index] = v
  // 在99999 比较情况下 选择排序和堆排序
    //排序结果 无 排序比较次数 4999950000 排序交换次数 99999 耗时 10019693000
    //排序结果 无 排序比较次数 0 排序交换次数 99999 耗时 12014000
}