扫码订阅《 Go语言算法与数据结构》或入驻星球,即可阅读文章!

GOLANG ROADMAP

阅读模式

  • 沉浸
  • 自动
  • 日常
首页
Go学习
  • Go学院

    • Go小课
    • Go小考
    • Go实战
    • 精品课
  • Go宝典

    • 在线宝典
    • B站精选
    • 推荐图书
    • 精品博文
  • Go开源

    • Go仓库
    • Go月刊
  • Go下载

    • 视频资源
    • 文档资源
Go求职
  • 求职服务

    • 内推互助
    • 求职助力
  • 求职刷题

    • 企业题库
    • 面试宝典
    • 求职面经
Go友会
  • 城市
  • 校园
推广返利 🤑
实验区
  • Go周边
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
author-avatar

GOLANG ROADMAP


首页
Go学习
  • Go学院

    • Go小课
    • Go小考
    • Go实战
    • 精品课
  • Go宝典

    • 在线宝典
    • B站精选
    • 推荐图书
    • 精品博文
  • Go开源

    • Go仓库
    • Go月刊
  • Go下载

    • 视频资源
    • 文档资源
Go求职
  • 求职服务

    • 内推互助
    • 求职助力
  • 求职刷题

    • 企业题库
    • 面试宝典
    • 求职面经
Go友会
  • 城市
  • 校园
推广返利 🤑
实验区
  • Go周边
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
  • 课程介绍

    • 《Go语言算法与数据结构》
  • 算法

    • 快速排序算法
    • 堆排序算法
    • 冒泡排序算法
    • 二分查找方法
    • 选择排序算法
    • 基数排序算法
    • 拓扑排序
    • 插入排序算法
    • 字符串匹配
    • 二叉搜索树
  • 数据结构

    • 图
    • 散列表
    • 堆
    • 链表
    • 跳跃表
    • 字典树

扫码订阅《 Go语言算法与数据结构》或入驻星球,即可阅读文章!

堆排序算法


GOLANG ROADMAP

# 堆排序算法

算法描述:首先建一个堆,然后调整堆,调整过程是将节点和子节点进行比较,将其中最大的值变为父节点,递归调整调整次数lgn,最后将根节点和尾节点交换再n次调整O(nlgn).

# 算法步骤

  • 创建最大堆或者最小堆(我是最小堆)
  • 调整堆
  • 交换首尾节点(为了维持一个完全二叉树才要进行收尾交换)
package sort

import "fmt"

//堆排序
func main() {
    arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12}
    fmt.Println(HeapSort(arr))
}
func HeapSortMax(arr []int, length int) []int {
    // length := len(arr)
    if length <= 1 {
        return arr
    }
    depth := length/2 - 1 //二叉树深度
    for i := depth; i >= 0; i-- {
        topmax := i //假定最大的位置就在i的位置
        leftchild := 2*i + 1
        rightchild := 2*i + 2
        if leftchild <= length-1 && arr[leftchild] > arr[topmax] { //防止越过界限
            topmax = leftchild
        }
        if rightchild <= length-1 && arr[rightchild] > arr[topmax] { //防止越过界限
            topmax = rightchild
        }
        if topmax != i {
            arr[i], arr[topmax] = arr[topmax], arr[i]
        }
    }
    return arr
}
func HeapSort(arr []int) []int {
    length := len(arr)
    for i := 0; i < length; i++ {
        lastlen := length - i
        HeapSortMax(arr, lastlen)
        if i < length {
            arr[0], arr[lastlen-1] = arr[lastlen-1], arr[0]
        }
    }
    return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
  • 堆排序算法
  • 算法步骤