排序算法:堆排序,golang实现
目录
前言
堆排序
代码示例
1. 算法包
2. 堆排序代码
3. 模拟程序
4. 运行程序
5. 从大到小排序
堆排序的思想
堆排序的实现逻辑
1. 构建最大堆
2. 排序
循环次数测试
假如 10 条数据进行排序
假如 20 条数据进行排序
假如 30 条数据进行排序
假设 5000 条数据,对比 冒泡、选择、插入、快速、归并
堆排序的适用场景
1. 大数据集排序
2. 外部排序
3. 优先级队列
4. 动态数据排序
前言
在实际场景中,选择合适的排序算法对于提高程序的效率和性能至关重要,本节课主要讲解"堆排序"的适用场景及代码实现。
堆排序
堆排序(Heap Sort)是一种基于比较的排序算法,它利用堆这种数据结构所设计。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。在堆排序算法中,我们通常采用最大堆(每个父节点的值都大于或等于其子节点的值)来进行排序。
代码示例
下面我们使用Go语言实现一个堆排序
1. 算法包
创建一个 pkg/algorithm.go
touch pkg/algorithm.go
(如果看过上节课的快速排序,则已存在该文件,我们就不需要再创建了)
2. 堆排序代码
打开 pkg/algorithm.go 文件,代码如下
从小到大 排序
package pkg// BubbleSort 冒泡排序
...// SelectionSort 选择排序
...// InsertionSort 插入排序
...// QuickSort 快速排序
...// partition 分区操作
...// HeapSort 堆排序
func HeapSort(arr []int) {n := len(arr)// 构建最大堆for i := n/2 - 1; i >= 0; i-- {heapify(arr, n, i)}// 一个个从堆顶取出元素for i := n - 1; i >= 0; i-- {// 移动当前根到末尾arr[i], arr[0] = arr[0], arr[i]// 调用 max heapify on the reduced heapheapify(arr, i, 0)}
}// heapify 将以 i 为根的子树调整为最大堆
func heapify(arr []int, n int, i int) {largest := i // 初始化最大为根l := 2*i + 1 // 左子节点r := 2*i + 2 // 右子节点// 如果左子节点大于根if l < n && arr[l] > arr[largest] {largest = l}// 如果右子节点大于当前的最大值if r < n && arr[r] > arr[largest] {largest = r}// 如果最大值不是根if largest != i {arr[i], arr[largest] = arr[largest], arr[i] // 交换// 递归地堆化受影响的子树heapify(arr, n, largest)}
}
3. 模拟程序
打开 main.go 文件,代码如下:
package mainimport ("demo/pkg""fmt"
)func main() {// 定义一个切片,这里我们模拟 10 个元素arr := []int{84, 353, 596, 848, 425, 849, 166, 521, 228, 573}fmt.Println("Original data:", arr) // 先打印原始数据pkg.HeapSort(arr) // 调用堆排序fmt.Println("New data: ", arr) // 后打印排序后的数据
}
4. 运行程序
go run main.go
能发现, Original data 后打印的数据,正是我们代码中定义的切片数据,顺序也是一致的。
New Data 后打印的数据,则是经过堆排序后的数据,是从小到大的。
5. 从大到小排序
如果需要 从大到小 排序也是可以的,在代码里,需要将两个 if 判断比较的 符号 进行修改。
修改 pkg/algorithm.go 文件:
package pkg// BubbleSort 冒泡排序
...// SelectionSort 选择排序
...// InsertionSort 插入排序
...// QuickSort 快速排序
...// partition 分区操作
...// HeapSort 堆排序
func HeapSort(arr []int) {n := len(arr)// 构建最大堆for i := n/2 - 1; i >= 0; i-- {heapify(arr, n, i)}// 一个个从堆顶取出元素for i := n - 1; i >= 0; i-- {// 移动当前根到末尾arr[i], arr[0] = arr[0], arr[i]// 调用 max heapify on the reduced heapheapify(arr, i, 0)}
}// heapify 将以 i 为根的子树调整为最大堆
func heapify(arr []int, n int, i int) {largest := i // 初始化最大为根l := 2*i + 1 // 左子节点r := 2*i + 2 // 右子节点// 如果左子节点小于根if l < n && arr[l] < arr[largest] {largest = l}// 如果右子节点小于当前的最大值if r < n && arr[r] < arr[largest] {largest = r}// 如果最大值不是根if largest != i {arr[i], arr[largest] = arr[largest], arr[i] // 交换// 递归地堆化受影响的子树heapify(arr, n, largest)}
}
只需要一丁点的代码即可
从 package pkg 算第一行,上面示例中在第四十四行代码,第四十九行代码,我们将 ">" 改成了 "<" ,这样就变成了 从大到小排序了
堆排序的思想
- 利用堆的性质:堆排序利用堆的性质,通过不断调整堆来使得每次都能从堆顶取出当前序列的最大(或最小)元素,从而达到排序的目的
- 原地排序:堆排序是一种原地排序算法,它只需要用到 O(1) 的额外空间来进行排序(除了输入的数组外,不需要使用其他数据结构)
- 不稳定性:堆排序是一种不稳定的排序算法,因为在调整堆的过程中,可能会改变相同元素的相对顺序
- 时间复杂度:堆排序的时间复杂度是 O(n log n),这主要来自于构建最大堆和每次调整堆的时间复杂度
堆排序的实现逻辑
堆排序主要分为两个步骤:
1. 构建最大堆
- 将待排序的序列构造成一个最大堆,此时,整个序列的最大值就是堆顶的根节点
- 构建最大堆的过程是从最后一个非叶子节点开始(即 n/2-1 位置,因为数组是从 0 开始索引的),对每个非叶子节点调用 heapify 函数,使其和其子树满足最大堆的性质
2. 排序
- 将堆顶元素(最大值)与堆数组的末尾元素进行交换,此时末尾就是最大值
- 由于堆的大小减少 1,我们再次将堆顶元素调整为最大值,以满足最大堆的性质
- 重复这个过程,直到堆的大小为 1,算法结束
循环次数测试
参照上面示例进行测试(因考虑到每次手动输入 10 条、20 条、30 条数据太繁琐,所以我写了一个函数,帮助我自动生成 0到1000 的随机整数)
假如 10 条数据进行排序
总计循环了 32 次
假如 20 条数据进行排序
总计循环了 79 次
假如 30 条数据进行排序
总计循环了 136 次
假设 5000 条数据,对比 冒泡、选择、插入、快速、归并
- 冒泡排序:循环次数 12,502,499 次
- 选择排序:循环次数 12,502,499 次
- 插入排序:循环次数 6,323,958 次
- 快速排序:循环次数 74,236 次
- 堆排序:循环次数 59,589 次
- 归并排序:循环次数 60,288 次
堆排序的适用场景
堆排序特别适用于以下场景
1. 大数据集排序
由于堆排序的时间复杂度是 O(n log n),在处理大数据集时效率较高
2. 外部排序
当数据太大,不能全部加载到内存时,可以使用堆排序进行外部排序,因为它只需要读取一次输入数据,然后逐步输出排序结果
3. 优先级队列
堆经常被用作优先级队列的实现方式,堆排序可以看作是从无序的优先队列中重建有序的优先队列的过程
4. 动态数据排序
当数据集合动态变化(如插入、删除操作频繁),堆排序的堆结构可以高效地维护数据的排序状态
总的来说,堆排序因其良好的最坏情况时间复杂度,以及对动态数据排序的友好性,在多种场景下都是非常有用的排序算法
相关文章:
排序算法:堆排序,golang实现
目录 前言 堆排序 代码示例 1. 算法包 2. 堆排序代码 3. 模拟程序 4. 运行程序 5. 从大到小排序 堆排序的思想 堆排序的实现逻辑 1. 构建最大堆 2. 排序 循环次数测试 假如 10 条数据进行排序 假如 20 条数据进行排序 假如 30 条数据进行排序 假设 5000 条数据…...
【网络安全入门】学习网络安全必须知道的77个网络基础知识
1、TCP/IP 协议的四层模型(网络接口层、网络层、传输层、应用层) TCP/IP 协议是互联网通信的基础,四层模型中,网络接口层负责与物理网络的连接;网络层主要处理 IP 数据包的路由和转发;传输层提供端到端的可…...
limit 以及分页 SQL 语句
目录 1. 作用 2. 演示 3. 分页 SQL 语句 1. 作用 获取结果集的一部分; 2. 演示 (1)如下,获取表的前三行; (2)只有一个数字,默认从 0 开始; (3&#x…...
mysql8.0规范
MySQL 数据库开发规范 目录 背景与目标规范列表 1. 库表设计 1.1 必须字段1.2 命名规范 2. 定义规范 2.1 约束规范2.2 类型规范 2.2.1 字段类型与长度2.2.2 状态字段数据类型2.2.3 布尔型2.2.4 varchar和text, json2.2.5 decimal(m,d) 3. 索引规范4. 其他规范5. SQL 使用 5.…...
现代前端架构介绍(第三部分):深入了解状态管理层及其对前端App的影响
远离JavaScript疲劳和框架大战,了解真正重要的东西 在第二部分中,我们讨论了功能架构的三个层次。其中一个就是状态管理层,今天我们将对其进行更深入的探讨。下面是现代前端架构系列的第三部分和最后一部分介绍。 状态管理,你可能…...
NLP与搜广推常见面试问题
1 auc指标 AUC的两种意义 一个是ROC曲线的面积另外一个是统计意义。从统计学角度理解,AUC等于随机挑选一个正样本和负样本时,模型对正样本的预测分数大于负样本的预测分数的概率。下图为搜广推场景下的一个计算auc的例子 2 GAUC指标 就是在推荐系统…...
Python怎么实现协程并发呢?
在Python中,实现协程并发主要是通过asyncio库来完成的。asyncio是Python 3.4中引入的标准库,用于编写单线程的并发代码。使用async和await关键字,你可以定义协程和等待其他协程的完成,而不需要创建额外的线程或进程。 下面是一个使…...
专治408开始的晚!8月一定要完成这些事!
八月份才开始408,那到考试最多也只有4-5个月的时间 别担心,可以复习两轮! 其实我一直建议大家408复习三轮,但是如果时间不够,那就要在复习质量上下功夫! 考408有一个好处,就是不用先确定学校…...
计算机毕业设计选题推荐-校内跑腿业务系统-Java/Python项目实战
✨作者主页:IT毕设梦工厂✨ 个人简介:曾从事计算机专业培训教学,擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…...
Unity命名验证工具类
在Unity开发中,经常需要验证变量名是否符合命名规范,同时避免使用C#的保留字作为变量名。本教程将演示如何创建一个简单的工具类来实现这一功能。 步骤 1:创建Unity命名验证工具类 首先,我们创建一个C#类,命名为Unit…...
基于cubeMX的STM32开启SPI及DMA
1、打开cubeMX后,设置SPI,如下图 2、设置SPI的DMA中断 3、DMA设置 4、SPI的GPIO设置 5、最后生成代码,可以看到工程文件中有dma.c和spi.c 6、使用举例:如幻彩灯的亮灭使用SPIDMA产生的信号波形来控制,在ws2812.c中调用…...
AI大模型技术的四大核心架构分析
AI大模型技术的四大核心架构演进之路 随着人工智能技术的飞速发展,大模型技术已经成为AI领域的重要分支。 深度剖析四大大模型技术架构:纯粹的Prompt提示词法、Agent Function Calling机制,RAG(检索增强生成)及Fine-…...
[C#]调用本地摄像头录制视频并保存
AForge.NET是一个基于C#框架设计的开源计算机视觉和人工智能库,专为开发者和研究者设计。它提供了丰富的图像处理和视频处理算法、机器学习和神经网络模型,具有高效、易用、稳定等特点。AForge库由多个组件模块组成,包括AForge.Imaging&#…...
opencv-图像基础变换
1,缩放 缩放是对图像的大小进行调整 缩放矩阵,相当于x和y乘一个常数 例如将图像放大两倍 import cv2 img cv2.imread(1.jpg) img cv2.resize(img, (400,400)) img cv2.resize(img, (0,0), fx3, fy1)#表示x方向扩大三倍,y方向不变 2&…...
xss漏洞(三,xss进阶利用)
本文仅作为学习参考使用,本文作者对任何使用本文进行渗透攻击破坏不负任何责任。 前言: 1,本文基于dvwa靶场以及PHP study进行操作,靶场具体搭建参考上一篇: xss漏洞(二,xss靶场搭建以及简单…...
git 迁移仓库的方法
git Git是一个开源的分布式版本控制系统,由Linus Torvalds在2005年创建,用于有效、高速地处理从小到大的项目管理。它最初是为Linux内核开发而设计的,但很快被广泛用于各种项目。 以下是Git的一些主要特性: 分布式架构ÿ…...
C# Where关键字
1. 泛型约束(Generic Constraints) 在泛型类、接口或方法的定义中,where关键字用于指定类型参数的约束。这些约束可以确保类型参数具有某些特定的属性。例如它是一个类、实现了某个接口、是另一个类型的派生类、具有无参构造函数等。 1.1 …...
《计算机组成原理》(第3版)第1章 计算机系统概论 复习笔记
第1章 计算机系统概论 一、计算机系统简介 (一)计算机的软硬件概念 1.计算机系统由“硬件”和“软件”两大部分组成 (1)所谓“硬件”,是指计算机的实体部分,如主机、外部设备等。 ࿰…...
达梦数据库的系统视图v$cachers
达梦数据库的系统视图v$cachers 达梦数据库的系统视图V$CACHERS的作用是显示缓存中的项信息,在 ini 参数 USE_PLN_POOL !0 时才统计。这个视图帮助数据库管理员监控和分析缓存的使用情况,优化数据库性能。通过查询V$CACHERS视图,可以获取缓存…...
电路元件基本知识详解
电路元件基本知识详解 在现代电子技术中,电路元件是构成各种电子电路的基本单元。它们各自具有不同的特性和功能,通过不同的连接方式实现多种多样的电路功能。本文将详细介绍几种常见的电路元件及其基本知识。 ### 一、电阻器 #### 1. 电阻器的基本概…...
从零开始写一个微信小程序
从零开始写一个微信小程序可以分为几个步骤。以下是一个详细的指南,帮助你从头到尾完成一个简单的微信小程序。 ### 一、准备工作 1. **注册微信小程序账号**: - 前往[微信公众平台](https://mp.weixin.qq.com/)注册一个小程序账号。 - 进行企业认证(个人账号需要申…...
07030405复杂可编程逻辑器件CPLD现场可编程阵列FPGA
复杂可编程逻辑器件CPLD&现场可编程阵列FPGA 7.3 复杂可编程逻辑器件CPLD7.3.1CPLD的结构 7.4现场可编程门阵列FPGA7.4.1FPGA实现逻辑功能的基本原理7.4.2FPGA结构简介1.可编程逻辑块2.I/O块3.可编程连线资源CPLD与FPGA的区别 7.5可编程逻辑器件开发过程简介编程条件 7.3 复…...
《雅思口语真经总纲1.0》话题实战训练笔记part1——5. Bus or taxi
《雅思口语真经总纲1.0》笔记——第四章:口语素材大全(part1、part2、part3回答准则及练习方法,不包括范例答案)★★★★★ 文章目录 Bus or taxiHou often do you take the bus?20240803答评价疑问 When was the first time you…...
《工程检索增强生成系统时的七个失败点》论文 AI 解读
周末使用 AI 速度了一篇 RAG 相关的论文,文中提到的【设计 RAG 系统时需要考虑的七个失败点】非常有价值,简单整理一下分享出来,大家如果感兴趣可以继续阅读原文。 论文名称:Seven Failure Points When Engineering a Retrieval A…...
每日一题——贪心算法
1005. K 次取反后最大化的数组和 - 力扣(LeetCode) 题解: 一开始有点理解错他的意思,以为是i是题目中会给出,所以一开始没有什么思路,然后当看了题解之后,就知道了原来i是自己订的,…...
Artix7系列FPGA实现SDI视频编解码+图像缩放+多路视频拼接,基于GTP高速接口,提供4套工程源码和技术支持
目录 1、前言工程概述免责声明 2、相关方案推荐本博已有的 SDI 编解码方案本博已有的FPGA图像缩放方案本博已有的已有的FPGA视频拼接叠加融合方案本方案的无缩放应用本方案在Xilinx--Kintex系列FPGA上的应用本方案在Xilinx--Zynq系列FPGA上的应用 3、详细设计方案设计原理框图S…...
HTTP 状态码详细介绍
超文本传输协议(Hypertext Transfer Protocol,HTTP)是一个简单的请求-响应协议,它通常运行在TCP之上。它指定了客户端可能发送给服务器什么样的消息以及得到什么样的响应。请求和响应消息的头以ASCII形式给出;而消息内…...
React前端面试每日一试 5.什么是受控组件和非受控组件?
在React中,受控组件和非受控组件是两种处理表单数据的方式。理解这两种方式对于管理和维护表单状态非常重要。 受控组件(Controlled Components) 受控组件是指那些表单数据完全由React组件的状态控制的组件。也就是说,表单元素的…...
代码随想录打卡第四十四天
代码随想录–动态规划部分 day 44 动态规划第11天 文章目录 代码随想录--动态规划部分一、力扣1143--最长公共子序列二、力扣1035--不相交的线三、力扣53--最大子数组和四、力扣392--判断子序列 一、力扣1143–最长公共子序列 代码随想录题目链接:代码随想录 给定…...
【JAVA】枚举类的使用:通过枚举类名称得到对应值进行输出
枚举类其实就是一个特殊的class。 /*** ClassName: CardType* Description:数字卡类型对应的文字卡类型*/ public enum CardType {NORMAL_CARD("金普卡"),BUSINESS_CARD("商务卡"),PRIVATE_CARD("黑金无限卡");private String cardName;CardTyp…...
网推网站/同城推广平台有哪些
今天终于把倒车考了,早上6点起床去赶班车,到了空港基地又换乘班车去考点,好远的哦,在嘉定了,用师傅的话说那里是真正的乡下,呵呵。10点到考点,然后就一直等到下午1点才轮到我们,还好…...
集团微网站建设/seo培训网
linux系统(CentOS7)虚拟机上安装oracle 11g,解决oracle图形界面卡住无法点击next问题参考文章: (1)linux系统(CentOS7)虚拟机上安装oracle 11g,解决oracle图形界面卡住无…...
做ppt可以赚钱网站/一件代发48个货源网站
在Java中,异常情况分为Exception(异常)和Error(错误)两大类,Java异常通常是指程序运行过程中出现的非正常情况,如用户输入错误、除数为零、需要处理的文件不存在、数组下标越界等,对…...
购物网站 功能/缅甸最新新闻
6种.net分布式缓存解决方式1. 使用内置ASP.NET Cache (System.Web.Caching) : https://msdn.microsoft.com/en-us/library/system.web.caching(vvs.110).aspx2. 使用System.Runtime.Caching: https://msdn.microsoft.com/en-us/library/system.runtime.caching(VS.100)…...
网站建设试用/谷歌seo推广服务
上图是我整理的Java面试题合集,包揽了基本所有技术栈:完整版Java面试题合集附答案,高清PDF下载 1. String 是最基本的数据类型吗 不是。Java 中的基本数据类型只有 8 个 :byte、short、int、long、float、double、char、boolean…...
游戏代理商/搜索引擎优化指的是
物理机安装ESXI6.7提示No Network Adapters的解决方案参考文章: (1)物理机安装ESXI6.7提示No Network Adapters的解决方案 (2)https://www.cnblogs.com/djlsunshine/p/11357591.html 备忘一下。...