跟着动画学Go数据结构之堆排序 #私藏项目实操分享#

简介: 跟着动画学Go数据结构之堆排序 #私藏项目实操分享#

堆排序

堆排序是一种树形选择排序算法。

image.png

堆排序过程

  1. 构建初始堆
  2. 在输出堆的顶层元素后,从上到下进行调整,将顶层元素与其左右子树的根节点进行比较,并将最小的元素交换到堆的顶部;然后不断调整直到叶子节点得到新的堆。

假如,{1, 7, 9, 2, 4, 6, 3, 5, 8} 建堆,然后进行堆排序输出。

动画显示

  1. 初始化堆,建堆操作图画演示:

首先根据无序序列 {1, 7, 9, 2, 4, 6, 3, 5, 8} 按照完全二叉树的顺序构建一棵完全二叉树,如图:

image.png

image.png

image.png

最终通过此次调整堆,得到新的堆为 [9, 8, 6, 7, 4, 1, 3, 5, 2] ,得到新的堆后开始堆排序过程

  1. 开始堆排序

构建完初始堆后,此时,我们可以进入堆排序,从上面的方法中,我们可以已知我们构建的最大堆的堆顶是最大的记录,可以可以将堆顶交换到最后一个元素的位置,然后执行堆顶下沉操作,然后再执行堆调整操作(新的堆顶也是最大值),直到剩余一个节点,得到一个有序序列。

image.png

此时,我们又可以进行堆调整操作,如下图:

image.png

堆调整完毕,开始把新的堆顶 8 和最后一个记录 2 进行交换,然后将堆顶下沉,调整为堆,如下图所示:

image.png

从此我们得到新的堆顶 7 ,然后把 7 跟最后一个元素 3 进行交换,7 下沉,然后堆调整,慢慢得到 6 ,5,如图所示:

image.png

然后是 3 下沉:

image.png

最后,堆顶 2 与最后一个记录 1 进行交换,只剩一个节点,堆排序结束,如下图所示:

image.png

我们得到的新的序列按序号读取数据,就是一个有序序列。

学习了这么久数据结构,这真的是第一次在自己画图过程中感受到堆排序的魅力,如果你看我的文章还是觉得有点懵,请去看陈小玉老师的《趣学数据结构》,真的是入门必备,讲得很详细了。

代码实现

最后,我们用代码来检验一下我们的动画过程是否正确,如下:

package main
import "fmt"
// 调整堆
func adjustHeap(array []int, currentIndex int, maxLength int) {
    var noLeafValue = array[currentIndex] // 当前非叶子节点
    // j 指向左孩子
    // 当前非叶子节点的左节点为:2 * currentIndex + 1
    for j := 2*currentIndex + 1; j <= maxLength; j = currentIndex*2 + 1 {
        if j < maxLength && array[j] < array[j+1] { // 如果有右孩子,且左孩子比右孩子小
            j++ // j 指向右孩子
        }
        if noLeafValue >= array[j] {
            break // 非叶子节点大于孩子节点,跳过不交换
        }
        array[currentIndex] = array[j] // 移动到当前节点的父节点
        currentIndex = j               // j 指向交换后的新位置,继续向下比较
    }
    array[currentIndex] = noLeafValue // 放在合适的位置
}
// 初始化堆
func createHeap(array []int, length int) {
    // 建堆
    for i := length / 2; i >= 0; i-- {
        adjustHeap(array, i, length-1)
    }
}
func heapSort(array []int, length int) {
    for i := length - 1; i > 0; i-- {
        array[0], array[i] = array[i], array[0]
        adjustHeap(array, 0, i-1)
    }
}
func main() {
    var unsorted = []int{1, 7, 9, 2, 4, 6, 3, 5, 8}
    var length = len(unsorted)
    fmt.Println("建堆之前:")
    for i := 0; i < length; i++ {
        fmt.Printf("%d,", unsorted[i])
    }
    fmt.Println()
    fmt.Println("建堆之后:")
    createHeap(unsorted, length)
    for i := 0; i < length; i++ {
        fmt.Printf("%d,", unsorted[i])
    }
    fmt.Printf("\n堆排序之后: \n")
    heapSort(unsorted, length)
    for i := 0; i < length; i++ {
        fmt.Printf("%d,", unsorted[i])
    }
}

运行结果:

[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 数据结构\堆排序\main.go"
建堆之前:
1,7,9,2,4,6,3,5,8,
建堆之后:
9,8,6,7,4,1,3,5,2,
堆排序之后: 
1,2,3,4,5,6,7,8,9,

可以看到,创建堆的结果 9,8,6,7,4,1,3,5,2 和排序结果 1,2,3,4,5,6,7,8,9 都是和我们图中的堆一样,所以说图看懂了代码也就有意思了。

image.png

相关文章
|
2月前
|
存储 Go 容器
深入探究Go语言中的数据结构
深入探究Go语言中的数据结构
63 3
|
4月前
|
JSON 运维 Go
Go 项目配置文件的定义和读取
Go 项目配置文件的定义和读取
|
1月前
|
Go API 数据库
Go 语言中常用的 ORM 框架,如 GORM、XORM 和 BeeORM,分析了它们的特点、优势及不足,并从功能特性、性能表现、易用性和社区活跃度等方面进行了比较,旨在帮助开发者根据项目需求选择合适的 ORM 框架。
本文介绍了 Go 语言中常用的 ORM 框架,如 GORM、XORM 和 BeeORM,分析了它们的特点、优势及不足,并从功能特性、性能表现、易用性和社区活跃度等方面进行了比较,旨在帮助开发者根据项目需求选择合适的 ORM 框架。
118 4
|
1月前
|
存储 JSON Go
如何在 Go 项目中隐藏敏感信息,比如避免暴露用户密码?
在Go语言开发中,用户信息管理常涉及敏感数据如密码的处理。为防止这些数据暴露给客户端,本文介绍了三种方法:使用JSON标签忽略字段、自定义序列化逻辑、使用数据传输对象(DTO),以确保用户数据的安全性。通过这些方法,可以有效控制数据输出,避免敏感信息泄露。
37 1
|
1月前
|
中间件 Go API
Go语言中几种流行的Web框架,如Beego、Gin和Echo,分析了它们的特点、性能及适用场景,并讨论了如何根据项目需求、性能要求、团队经验和社区支持等因素选择最合适的框架
本文概述了Go语言中几种流行的Web框架,如Beego、Gin和Echo,分析了它们的特点、性能及适用场景,并讨论了如何根据项目需求、性能要求、团队经验和社区支持等因素选择最合适的框架。
103 1
|
2月前
|
SQL 关系型数据库 MySQL
Go语言项目高效对接SQL数据库:实践技巧与方法
在Go语言项目中,与SQL数据库进行对接是一项基础且重要的任务
98 11
|
2月前
|
Go
使用go语言将A助手加入项目中
使用go语言将A助手加入项目中
27 2
|
2月前
|
算法 搜索推荐
数据结构与算法学习十八:堆排序
这篇文章介绍了堆排序是一种通过构建堆数据结构来实现的高效排序算法,具有平均和最坏时间复杂度为O(nlogn)的特点。
84 0
数据结构与算法学习十八:堆排序
|
2月前
|
存储 Kubernetes Go
Go语言项目组织架构
Go语言项目组织架构
|
4月前
|
API
企业项目迁移go-zero实战(二)
企业项目迁移go-zero实战(二)