算法之堆排序golang

川长思鸟来 2022-06-11 00:12 173阅读 0赞

package main
    
    import (
        "fmt"
    )
    
    func swap(i, j int, a []int) {
        a[j], a[i] = a[i], a[j]
    
    }
    func headAdjust(a []int, start, end int) { 
        temp := a[start]
    
        for i := 2*start + 1; i <= end; i *= 2 { 
           // 左右孩子的节点 2i+1. 2i+2
    
           //选择出左右孩子较大的下标
            if i < end && a[i] < a[i+1] { 
                i++
            }
    
            if temp <= a[i] {
                break //已为大顶堆 保持稳定性
            }
            a[start] = a[i] //将子节点上移
            start = i      //下一轮帅选
    
        }
        a[start] = temp //插入正确的位置
    }
    
    func HeatSort(a []int) {
        length := len(a)
        if length == 0 {
            return
        }
    
        for i := length / 2; i >= 0; i-- { 
            headAdjust(a, i, length-1)
        }
    
        for j := length - 1; j >= 0; j-- { 
            swap(0, j, a)
            headAdjust(a, 0, j-1)
        }
    
    }
    
    func main() {
        a := []int{
       34, 52, 12, 45, 56, 10, 35}
        HeatSort(a)
    
        fmt.Println(a)
    
    }

➜  headSort time go run headSort.go
    [10 12 34 35 52 45 56]
    go run headSort.go 0.14s user 0.46s system 86% cpu 0.702 total

发表评论取消回复

表情：

评论列表（有 0 条评论，173人围观）

还没有评论，来说两句吧...

相关阅读

相关排序算法之堆排序

参考文章：[https://blog.csdn.net/u010452388/article/details/81283998][https_blog.csdn.net_u01

傷城~/ 2023年07月21日 03:21/ 0 赞/ 105 阅读

相关排序算法之堆排序

堆排序的时间复杂度O(N\logN),额外空间复杂度O(1)，是一个不稳定性的排序 ![在这里插入图片描述][20200806095320516.gif] 准备堆的

╰+哭是因爲堅強的太久メ/ 2023年02月18日 14:15/ 0 赞/ 10 阅读

相关排序算法之堆排序

排序算法-----堆排序堆就是父节点值大于(大顶堆)子节点值或者父节点的值小于(小顶堆)子节点的值的完全二叉树，利用堆可以进行数组排序，如果要进行从小到大排序就

爱被打了一巴掌/ 2022年11月07日 04:13/ 0 赞/ 197 阅读

相关排序算法之堆排序

同样的先上这张图 ![Center][] 下面看一种较为复杂的选择排序 ——堆排序：首先来看一下什么是堆，堆用一个一维的数组模拟二叉树的结构，即堆数组的第一个元素

短命女/ 2022年09月25日 15:22/ 0 赞/ 209 阅读

相关排序算法之堆排序

堆排序> 在上一篇中提到了大小堆的问题，大小堆的一个应用就是堆排序，那仫什仫是堆排序呢？相对于我们经常使用的冒泡，选择以及直接插入排序，堆排序又存在什仫样不同的地方？我就

Love The Way You Lie/ 2022年07月16日 08:44/ 0 赞/ 223 阅读

相关排序算法之堆排序

问题描述：输入一个原始数列，把它进行升序排序，从小到大输出。例如：给定数列如下： 5 15 99 45 12 1 90 19 33 41 排序后的结果为： 1

雨点打透心脏的1/2处/ 2022年06月14日 02:39/ 0 赞/ 220 阅读

相关 C++排序算法之堆排序

堆排序算法 1、算法介绍堆是一种数据结构，可以把堆看成一棵完全二叉树，这可完全二叉树满足：任何一个非叶子结点的值都不大于（或者不小于）其左右孩子结点的值。若父

超、凢脫俗/ 2022年06月12日 02:36/ 0 赞/ 205 阅读

相关算法之堆排序golang

package main import ( "fmt" ) func swap(i, j int, a []

川长思鸟来/ 2022年06月11日 00:12/ 0 赞/ 174 阅读

相关排序算法之堆排序

堆的定义：堆实际上是一棵完全二叉树。堆满足两个性质: 1. 堆的每一个父节点都大于（或小于）其子节点； 2. 堆的每个左子树和右子树也是一个堆。堆的每个左子树

柔情只为你懂/ 2022年04月16日 04:59/ 0 赞/ 279 阅读

相关选择排序算法之堆排序

平均时间复杂度均为O(nlogn)，它也是不稳定排序。参考 [https://www.cnblogs.com/chengxiao/p/6129630.html][https

秒速五厘米/ 2022年02月24日 01:20/ 0 赞/ 312 阅读