排序方法——堆排序

文章目录

  • 一、堆的概念
  • 二、向下调整法
  • 三、堆排序
    • 建堆
    • 排序
  • 四、 完整代码

一、堆的概念


  堆的概念:一个按照完全二叉树的储存方式存储的一维数组我们称之为堆。


  堆可以分为大堆和小堆:
  大堆:二叉树中父亲节点的值都比自己的孩子节点的值大;
  小堆:二叉树中父亲节点的值都比自己的孩子节点的值小;
在这里插入图片描述
  这就是很明显的一组大小堆。
  堆排序的实现就是在对的基础上完成的。

二、向下调整法

  实现堆排序,用向下调整法时间复杂度最低
下面是向下调整的代码:

void Swap(int* x, int* y)
{int ret = *x;*x = *y;*y = ret;
}//降序建小堆
//升序建大堆
void AdjustDown(int* arr, int n, int father)
{                 // arr为数组 n为数组元素个数  father为当前数组下标//假设左孩子大int child = 2 * father + 1;while (child < n)//结束条件为到达了最后一层,最后一层没有孩子{//比较左右孩子,找出最大的孩子//if (child + 1 < n && arr[child + 1] < arr[child])//小堆, 降序if (child + 1 < n && arr[child + 1] > arr[child])//大堆, 升序{   //child+1<n是为了防止数组越界,    child++; //如果右孩子大于(小于)左孩子,child就加1}//if (arr[father] > arr[child])//小堆, 降序if (arr[father] < arr[child])//大堆, 升序 {Swap(&arr[father], &arr[child]);//father的值小于child的值,让二者交换father = child;  //再次进行下一组的交换,重新定义father和childchild = 2 * father + 1;}else{break;}}}

  以上就是向下调整法建大/小堆的过程。

三、堆排序

  建好堆以后就开始进行排序了,即将此时堆里的数值从上向下梳理一遍,使其变的有序。

  后面我们以大堆排升序为例进行讲解。

建堆

自定义一个函数HeapSort,用来进行堆排序

void HeapSort(int* arr, int n)
{//向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--) //(n - 1 - 1) / 2是最后一个有孩子的父节点{AdjustDown(arr, n, i);}
}

  假设有一个数组:arr[ ] = {2, 8, 9, 4, 7, 5, 6, 1, 3, 10}
在这里插入图片描述
  接下来,根据代码对数组元素进行比较:从以数字7为父节点开始进行调整
在这里插入图片描述
以上是向上调整建堆的全过程,最终得到数组arr[ ] = {10, 8, 9, 4, 7, 5, 6, 1, 3, 2}。
在这里插入图片描述

排序

  建完堆就该排序了

void HeapSort(int* arr, int n)
{//向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, n, i);}int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);end--;}
}

  变量end代表数组最后一个元素下标,排序需要遍历数组,所以end也可做完while循环的判断条件。
  这里将arr[0]与arr[end]交换,再进行向下调整,遍历整个数组,结束后数组变为有序数组,堆排序也就完成了。


  首先,将2和10进行交换
在这里插入图片描述
  从上向下依次进行比较,较大的数往下走,较小的数往上走。
在这里插入图片描述

以上是一次循环的过程,后面的循环同理,最后就会的到一组有序的数组。
在这里插入图片描述
  每一次循环结束后,end–, 继续将arr[0]与arr[end]交换,继续进行同样的排序。

在这里插入图片描述

四、 完整代码

//堆排序
//降序建小堆
//升序建大堆
void Swap(int* x, int* y)
{int ret = *x;*x = *y;*y = ret;
}void AdjustUp(int* arr, int child)
{int father = (child - 1) / 2;//while (child > 0)while(father >= 0){if (arr[father] < arr[child])//大堆  升序//if (arr[father] > arr[child])//小堆  降序{Swap(&arr[father], &arr[child]);child = father;father = (child - 1) / 2;}else{break;}}
}void AdjustDown(int* arr, int n, int father)
{//假设左大int child = 2 * father + 1;while (child < n){//找出最大的孩子//if (child + 1 < n && arr[child + 1] < arr[child])//小堆, 降序if (child + 1 < n && arr[child + 1] > arr[child])//大堆, 升序{child++;}//if (arr[father] > arr[child])//小堆, 降序if (arr[father] < arr[child])//大堆, 升序{Swap(&arr[father], &arr[child]);father = child;child = 2 * father + 1;}else{break;}}}void HeapSort(int* arr, int n)
{//向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, n, i);}//向上调整建堆/*for (int i = 1; i < n; i++){AdjustUp(arr, i);}*/int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);end--;}
}int main()
{int arr[] = { 2,8,9,4,7,5,6,1,3,10 };int sz = sizeof(arr) / sizeof(arr[0]);HeapSort(arr, sz);for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/337844.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

阿里云部署nodejs

目录 1、安装node.js 1-1 进入opt/software 1-2 下载node.js安装包 1-3 解压 2 配置环境变量 2-1 vim中配置环境变量 2-2 命令行中保存环境变量 2-3 检查安装版本 2-3 更换镜像 3、上传node.js项目 1-1 启动项目 1-2 配置对应的安全组 ​编辑 4、pm2启动多个node项…

运维开发.Kubernetes探针与应用

运维系列 Kubernetes探针与应用 - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this article:https://blog.csdn.net/qq_28550263…

SQL—DQL(数据查询语言)之小结

一、引言 在前面我们已经学习完了所有的关于DQL&#xff08;数据查询语言&#xff09;的基础语法块部分&#xff0c;现在对DQL语句所涉及的语法&#xff0c;以及需要注意的事项做一个简单的总结。 二、DQL语句 1、基础查询 注意&#xff1a; 基础查询的语法是&#xff1a;SELE…

移动端性能测试(android/ios)

solox官网 https://github.com/smart-test-ti/SoloX solox简介 实时收集android/ios性能的工具&#xff0c;Android设备无需Root&#xff0c;iOS设备无需越狱。有效解决Android和iOS性能的测试和分析挑战。 solox安装 环境准备 python安装3.10以上的 python官网下载地址…

cocos creator 3.x实现手机虚拟操作杆

简介 在许多移动游戏中&#xff0c;虚拟操纵杆是一个重要的用户界面元素&#xff0c;用于控制角色或物体的移动。本文将介绍如何在Unity中实现虚拟操纵杆&#xff0c;提供了一段用于移动控制的代码。我们将讨论不同类型的虚拟操纵杆&#xff0c;如固定和跟随&#xff0c;以及如…

[AI OpenAI] 推出ChatGPT Edu

一种负担得起的解决方案&#xff0c;帮助大学将AI负责任地引入校园。 我们宣布推出ChatGPT Edu&#xff0c;这是一个专为大学设计的ChatGPT版本&#xff0c;旨在负责任地向学生、教职员工、研究人员和校园运营部署AI。ChatGPT Edu由GPT-4o提供支持&#xff0c;能够跨文本和视觉…

iPad里的图片如何导出 iPad的照片如何管理

我们的设备中充满了各种重要的照片和视频&#xff0c;特别是iPad&#xff0c;作为苹果公司的一款强大的平板电脑&#xff0c;它不仅能够捕捉生活中的精彩瞬间&#xff0c;还可以存储和展示我们珍贵的回忆。然而&#xff0c;随着照片数量的不断增加&#xff0c;有效地管理和导出…

IO流(1)

定义&#xff1a;存取和读取数据的解决方案 作用&#xff1a;用于读写数据&#xff08;本地文件、网络&#xff09; 分类&#xff1a; 一种是&#xff1a;输出流和输入流。 一种是&#xff1a;字节流和字符流。 字节流 字节流——FileOutputStream&#xff08;字节输出流&…

【常见的六大排序算法】插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序

个人主页 创作不易&#xff0c;感谢大家的关注&#xff01; 文章目录 前言 &#x1f3a1;一、插入排序&#x1f332;二、希尔排序&#x1f389;三、选择排序&#x1f380;四、冒泡排序&#x1f698;五、堆排序&#x1f6f5;六、快速排序1. Hoare版本2. 挖坑法3. 前后指针法4. 非…

VLAN的概念及优势

文章目录 VLAN的概念及优势分割广播域 广播域vlanVLAN的优势 VLAN的种类静态VLAN动态VLAN 静态VLAN的配置静态VLAN范围配置静态VLAN的步骤 TRUNK介绍与配置三层交换机转发原理三层交换技术mls基于CEF的MLSCEF是一种基于拓补转发的模型 三层交换机的配置层 VLAN的概念及优势 分…

使用onnxruntime加载YOLOv8生成的onnx文件进行目标检测

在网上下载了60多幅包含西瓜和冬瓜的图像组成melon数据集&#xff0c;使用 LabelMe 工具进行标注&#xff0c;然后使用 labelme2yolov8 脚本将json文件转换成YOLOv8支持的.txt文件&#xff0c;并自动生成YOLOv8支持的目录结构&#xff0c;包括melon.yaml文件&#xff0c;其内容…

C++的第一道门坎:类与对象(二)

目录 一.类中生成的默认成员函数详解 0.类的6个默认成员函数 1.构造函数 1.1概念 1.2特性 2.析构函数 2.1概念 2.2特性 3.拷贝构造函数 3.1概念 3.2特性 3.3拷贝构造的使用方法 4.运算符重载 5.赋值运算符重载 6.const修饰函数 7.取地址及const取地址操作符重载…

【漯河市人才交流中心_登录安全分析报告-Ajax泄漏滑动距离导致安全隐患】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞…

Windows10(家庭版)中DockerDesktop(docker)的配置、安装、修改镜像源、使用

场景 Windows10中Docker的安装与遇到的那些坑: Windows10中Docker的安装与遇到的那些坑_在 docker.core.logging.httpclientexceptionintercept-CSDN博客 上面讲Docker Desktop在windows10非家庭版上的安装&#xff0c;如果是家庭版&#xff0c;则需要执行如下步骤。 注&am…

【python】OpenCV—Tracking(10.2)

文章目录 BackgroundSubtractorcreateBackgroundSubtractorMOG2createBackgroundSubtractorKNN BackgroundSubtractor Opencv 有三种背景分割器 K-Nearest&#xff1a;KNN Mixture of Gaussian&#xff08;MOG2&#xff09; Geometric Multigid&#xff08;GMG&#xff09; …

K210视觉识别模块学习笔记4: 训练与使用自己的模型_识别字母

今日开始学习K210视觉识别模块: 模型训练与使用_识别字母 亚博智能的K210视觉识别模块...... 固件库: maixpy_v0.6.2_52_gb1a1c5c5d_minimum_with_ide_support.bin 文章提供测试代码讲解、完整代码贴出、测试效果图、测试工程下载 这里也算是正式开始进入到视觉识别的领域了…

matplotlib ---词云图

词云图是一种直观的方式来展示文本数据&#xff0c;可以体现出一个文本中词频的使用情况&#xff0c;有利于文本分析&#xff0c;通过词频可以抓住一篇文章的重点 本文通过处理一篇关于分析影响洋流流向的文章&#xff0c;分析影响洋流流向的主要因素都有哪些 文本在文末结尾 …

基于Freertos的工训机器人

一. 工训机器人 V1 1. 实物 将自制的F4开发板放置车底板下方&#xff0c;节省上方空间&#xff0c;且能保证布线方便整齐。 2. SW仿真 使用SolidWorks进行仿真&#xff0c;且绘制3D打印件。 工训仿真 3.3D打印爪测试 机械爪测试 二. 工训机器人 V2 1. 实物 工训机器人V2不同于…

IDEA 打开项目后看不到项目结构怎么办?

1、先把这个项目从 IDEA 中移除 2、再重新打开或导入 3、如果还没有解决&#xff0c;就先把这个项目拷贝出来把原来的路径上的项目给删除&#xff0c;然后再把拷贝后的项目放在一个路径下&#xff0c;再打开就可以了

沟通程序化(1):跟着鬼谷子学沟通—“飞箝”之术

沟通的基础需要倾听&#xff0c;但如果对方听不进你的话&#xff0c;即便你说的再有道理&#xff0c;对方也很难入心。让我们看看鬼谷子的“飞箝”之术能给我们带来什么样的启发吧&#xff01; “飞箝”之术&#xff0c;源自中国古代兵法家、纵横家鼻祖鬼谷子的智慧&#xff0…