美文网首页
常见的排序算法-2.1 选择排序(堆排序)

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

作者: yulekwok | 来源:发表于2020-04-22 21:44 被阅读0次

    选择排序的优化方案(堆排序)

    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
    }
    

    相关文章

      网友评论

          本文标题:常见的排序算法-2.1 选择排序(堆排序)

          本文链接:https://www.haomeiwen.com/subject/islibhtx.html