当前位置: 首页 > news >正文

【数据结构初阶】堆排序

目录

前言

概念

堆排序的实现

1.建堆

 (1)堆向上调整算法

(2)堆的向下调整算法

2. 利用堆删除思想来进行排序

3.堆排序的时间复杂度

4.源码

总结


前言

前边我们学习了堆的实现,对堆的每个接口都进行了详细的讲解,所以这篇文章就来看一看堆到底有哪些应用。


概念

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:

  1. 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
  2. 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;

堆排序的平均时间复杂度为 Ο(nlogn)。

我们之前学习的冒泡排序的时间复杂度为o(n^2),此处的堆排序确是Ο(nlogn),这样直接看并不能看出堆排序的优势,如果我们使用数字代入就会发现,如果我们有1000个数,进行排序时,冒泡排序是100万次,若是堆排序只需1万次,对于更大的数差别也会更大,所以堆排序是很有优势的。

堆排序的实现


 

1.建堆

我们根据上节课的学习,我们知道了向上调整算法和向下调整算法,他们都可以建立一个堆。

我们要切记,需要升序排列时要建一个大堆,需要降序排列时要建一个小堆。

 (1)堆向上调整算法

现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们从第二个位置向上调整,直到最后一个位置的数为止。
​
void hpSort(int* a, int n)
{assert(a);//从第二个数开始向上调整for (int i = 1; i < n; i++){adjustUp(a, i);}
}​

(2)堆的向下调整算法

现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。

 有人可能认为向下调整算法的时间复杂度为o(n*log2n),其实并不是,时间复杂度其实为o(n),由于在倒数第二层时,每个元素只调整了一次,倒数第三层调整了两次,也可以通过数学公式来证明,通过错位相减法,最终得到了向下调整算法的时间复杂度为o(n)。

 

void hpSort(int* a, int n)
{assert(a);//从非叶子结点开始向下调整for (int i = (n-1)-1/2; i >= 0; i--){adjustDown(a, n, i);}
}

从非叶子结点开始调整,可以从最后一个结点的父节点处开始,进行向下调整,直至调整到根节点。


2. 利用堆删除思想来进行排序

(1)当我们要对数据进行降序排列时,我们先建立一个小堆,即父节点的数据小于子节点的数据。

(2)将最后一个结点与第一个结点互换,此时得到的最后一个结点的数据就是最小的数。

(3)此时对第一个结点向下调整,使其恢复成为一个小堆,此时堆顶元素就是整个堆中次小的数。

(4)此时,我们把最后一个结点与原来结点分离,只是看作分离,只是将其余结点从新进行之前的操作,直至堆的大小为1。

 

 

void hpSort(int* a, int n)
{assert(a);//从第二个数开始向上调整/*for (int i = 1; i < n; i++){adjustUp(a, i);}*///从非叶子结点开始向下调整for (int i = (n-1)-1/2; i >= 0; i--){adjustDown(a, n, i);}for(int end=n - 1 ; end > 0 ; end--){swap(&a[0], &a[end]);adjustDown(a, end ,0);}
}

 


3.堆排序的时间复杂度

我们知道了向下调整算法来建堆的时间复杂度为o(n),所以我们选择向下调整算法来建堆,在建完堆之后,我们就进行交换并且向下调整,排序的时间复杂度为o(n*log2n),所以总和的时间复杂度为o(n*log2n)。

4.源码

hpsort.c

void hpSort(int* a, int n)
{assert(a);//从第二个数开始向上调整/*for (int i = 1; i < n; i++){adjustUp(a, i);}*///从非叶子结点开始向下调整for (int i = (n-1)-1/2; i >= 0; i--){adjustDown(a, n, i);}for(int end=n - 1 ; end > 0 ; end--){swap(&a[0], &a[end]);adjustDown(a, end ,0);}
}

test.c

void test1()
{//TestTopk();int a[] = { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 };for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i){printf("%d ", a[i]);}printf("\n");hpSort(a, sizeof(a) / sizeof(a[0]));for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i){printf("%d ", a[i]);}printf("\n");}

总结

今天我们学习了堆排序的概念,实现,以及时间复杂度,过两天我会继续发布关于各种排序的文章,希望大家支持。

相关文章:

【数据结构初阶】堆排序

目录 前言 概念 堆排序的实现 1.建堆 &#xff08;1&#xff09;堆向上调整算法 &#xff08;2&#xff09;堆的向下调整算法 2. 利用堆删除思想来进行排序 3.堆排序的时间复杂度 4.源码 总结 前言 前边我们学习了堆的实现&#xff0c;对堆的每个接口都进行了详细的讲…...

Day5: platformDriver-1

Platform Driver (1) Linux kernel中大部分设备可以归结为平台设备&#xff0c;因此大部分的驱动是平台驱动&#xff08;patform driver&#xff09; 什么是平台设备 平台设备是linux的设备模型中一类设备的抽象。 内核中的描述&#xff1a; Platform devices are devices t…...

开发手册——一、编程规约_7.控制语句

这篇文章主要梳理了在java的实际开发过程中的编程规范问题。本篇文章主要借鉴于《阿里巴巴java开发手册终极版》 下面我们一起来看一下吧。 1. 【强制】在一个 switch 块内&#xff0c;每个 case 要么通过 break / return 等来终止&#xff0c;要么注释说明程序将继续执行到哪…...

python每日学9 : windows上配置gitee的远程仓库,git的初步使用

在开发中&#xff0c;如果遇到复杂的项目&#xff0c;使用版本控制是非常有必要的&#xff0c;如果涉及到多端开发&#xff0c;那么还需要使用远程仓库。本文作个简单记录&#xff0c;记录下git初步使用。 1 下载与安装 git还有几个ui版本&#xff0c;但是开始使用的话&#…...

精确率与召回率,ROC曲线与PR曲线

精确率与召回率&#xff0c;ROC曲线与PR曲线 在机器学习的算法评估中&#xff0c;尤其是分类算法评估中&#xff0c;我们经常听到精确率(precision)与召回率(recall)&#xff0c;ROC曲线与PR曲线这些概念&#xff0c;那这些概念到底有什么用处呢&#xff1f; 首先&#xff0c…...

现代操作系统——Linux架构与学习

小白的疑惑 在我决定从事嵌入式&#xff08;应用层&#xff09;方面的工作时&#xff0c;我查询了大量资料该如何学习&#xff0c;几乎所有观点不约而同的都指向了学习好Linux&#xff0c;大部分工作都是在Linux环境下来进行工作的。于是我雄心勃勃的去下载Linux&#xff0c;可…...

中文代码82

PK 嘚釦 docProps/PK 嘚釦羸 r docProps/app.xml潙蚽?勶曻Q顗濔S? 錞礖剅D柍珘m?鳞?ぷ辷f硌?2?upc厭Y樐8 rU y搪m眾&a?珪?紓 玺鶋瑣襚? ?i嘲rN?布倖儇?攊橌??嚗猝)芻矂2吟腊K湞?CK臶>鸘\?ΔF滋齢q旮T?桀?;偉 A軥v蕯朾偤佷3?е…...

顺序表(一篇带你掌握顺序表)

目录 一、顺序表是什么 1.1 概念 1.2 分类 1.3 结构 二、顺序表的基本操作 2.1 前绪准备 2.2 初始化 2.3 扩容 2.5 尾插 2.6 打印 2.7 尾删 2.8 头插 2.9 头删 2.10 在pos位置插入 2.11 删除pos位置的数据 2.12 查找 三、完整代码 3.1 Test.c文件 3.2 SeqList.h…...

【SpringCloud】SpringCloud教程之Feign实战

目录前言SpringCloud Feign远程服务调用一.需求二.两个服务的yml配置和访问路径三.使用RestTemplate远程调用(order服务内编写)四.构建Feign(order服务内配置)五.自定义Feign配置(order服务内配置)六.Feign配置日志(oder服务内配置)七.Feign调优(order服务内配置)八.抽离Feign前…...

嵌入式linux必备内存泄露检测神器

Valgrind介绍 Valgrind是一个可移植的动态二进制分析工具集&#xff0c;主要用于发现程序中的内存泄漏、不合法内存访问、使用未初始化的内存、不正确的内存释放以及性能问题等&#xff0c;可在Linux和Mac OS X等平台上使用。 Valgrind由多个工具组成&#xff0c;其中最常用的…...

设计模式之行为型模式

四、行为型模式 行为型模式用于描述程序在运行时复杂的流程控制&#xff0c;即描述多个类或对象之间怎样相互协作共同完成单个对象都无法单独完成的任务&#xff0c;它涉及算法与对象间职责的分配。 行为型模式分为类行为模式和对象行为模式&#xff0c;前者采用继承机制来在…...

解密 三岁的三岁到底为什么叫做三岁?

机缘 那一年&#xff0c;一次奇奇怪怪的挫折与一次奇奇怪怪的成长。 在学习Python的路上总觉得少了点什么&#xff0c;是心情&#xff1f;是机遇&#xff1f;还是力量&#xff1f; 都不是又都是&#xff01; 缺少一个实践和记忆的平台 记性不好是硬伤 前一天学的下一秒就忘记了…...

id选择器

id选择器可以为特定的id的标签进行css美化 使用方法&#xff1a; 标签内设好 id值&#xff0c; CSS的id选择器以“#id名”来调用 注意 所有标签都有id值id属性值类似于身份证号码&#xff0c;在一个页面中是唯一的值&#xff0c;不可重复一个标签上只能有一个id属性值一个id属性…...

《科技之巅3》读书笔记

文章目录书籍信息人工智能&#xff0c;“吃一堑长一智”的机器人机交互&#xff0c;为解决“交流障碍”问题而生硬件与算法&#xff0c;好马还需好鞍模式创新&#xff0c;赋予技术新的定义云与数据共享&#xff0c;灵活应对信息的爆发式增长“机器人”&#xff0c;从电影和小说…...

18.用于大型程序的工具

文章目录用于大型程序的工具18.1异常处理18.1.1抛出异常栈展开栈展开过程中对象被自动销毁析构函数与异常异常对象18.1.2捕获异常查找匹配的处理代码重新抛出捕获所有异常的处理代码18.1.3函数try语句块与构造函数18.1.4noexcept异常说明违反异常说明异常说明的实参noexcept运算…...

mysql一主键uuid和自增的选择

文章目录 1.自增ID的优缺点1.1 优点1.2 缺点1.3 不适合以自增ID主键作为主键的情况2.UUID作为主键2.1 介绍2.2 优点2.3 缺点3.有序UUID作为主键3.1 介绍3.2 演示使用3.2.1 前提知识3.2.1.1 数据类型 - binary3.2.1.2 函数 - hex()3.2.1.3 函数 - unhex()3.2.2 数据库层3.2.3 JA…...

【EDA工具使用】——VCS和Verdi的联合仿真的简单使用

目录 1.芯片开发所需的工具环境 2.编译仿真工具 3.三步式混合编译仿真&#xff08;最常用&#xff09;​编辑 4.两步式混合编译仿真​编辑 5.VCS的使用 ​6.verdi的使用 1.产生fsdb文件的两种方法​编辑 1.芯片开发所需的工具环境 2.编译仿真工具 3.三步式混合编译仿真…...

【Java学习笔记】4.Java 对象和类

前言 本章介绍Java的对象和类。 Java 对象和类 Java作为一种面向对象语言。支持以下基本概念&#xff1a; 多态继承封装抽象类对象实例方法重载 本节我们重点研究对象和类的概念。 对象&#xff1a;对象是类的一个实例&#xff08;对象不是找个女朋友&#xff09;&#x…...

39. 实战:基于api接口实现视频解析播放(32接口,窗口化操作,可导出exe,附源码)

目录 前言 目的 思路 代码实现 需要导入的模块 1. 导入解析网站列表&#xff0c;实现解析过程 2. 设计UI界面 3. 设置窗口居中和循环执行 4. 注意事项 完整源码 运行效果 总结 前言 本节将类似34. 实战&#xff1a;基于某api实现歌曲检索与下载&#xff08;附完整…...

基于灵动 MM32 微控制器的便携式血氧仪方案

基于灵动 MM32 微控制器的便携式血氧仪&#xff1a; - Cortex-M0() 最高主频 72MHz 可实现血氧饱和度信号采集、算法操作和 LED 显示操作 - 高性能的 1Msps 12b ADC 能对光电采样结果进行大数据量的暂存和处理&#xff0c;提高采样的效率并有助于对结果做高精度的计算 - 100…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

C++_哈希表

本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、基础概念 1. 哈希核心思想&#xff1a; 哈希函数的作用&#xff1a;通过此函数建立一个Key与存储位置之间的映射关系。理想目标&#xff1a;实现…...

【版本控制】GitHub Desktop 入门教程与开源协作全流程解析

目录 0 引言1 GitHub Desktop 入门教程1.1 安装与基础配置1.2 核心功能使用指南仓库管理日常开发流程分支管理 2 GitHub 开源协作流程详解2.1 Fork & Pull Request 模型2.2 完整协作流程步骤步骤 1: Fork&#xff08;创建个人副本&#xff09;步骤 2: Clone&#xff08;克隆…...