选择排序的优化方案(堆排序)
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
}
网友评论