堆排序----C语言数据结构

目录

    • 引言
  • 堆排序的实现
    • **堆的向下调整算法**
  • 对排序的时间复杂度
    • 建堆的时间复杂度:
    • 排序过程的时间复杂度:
    • 总体时间复杂度:

引言

堆排序(Heap Sort)是一种基于比较的排序算法,利用堆的数据结构来实现。它的时间复杂度为O(n log n),并且是原地排序算法,不需要额外的存储空间,这使得它在空间复杂度方面具有优势。

堆排序的关键在于构建和维护堆的性质。虽然堆排序的时间复杂度较好,但在实际应用中,由于其不具备插入和删除操作的优势,因此在一些特殊方面很少被选择。

堆排序的实现

堆排序实现的基本思路为:

  1. 建堆
    升序:建大堆
    降序:建小堆
  2. 利用堆删除思想来进行排序
    建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序。
    在这里插入图片描述

堆的向下调整算法

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

void Swap(int* a, int* b)
{int c = *a;*a = *b;*b = c;
}void AdjustDwon(int* a, int n, int parent)
{int child = parent * 2 + 1;while(child < n){if (child + 1 < n && a[child + 1] > a[child]){//先假设左孩子最小,不成立便改为右孩子child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child ;child = parent * 2 + 1;}elsebreak;}
}

在一个堆中,根节点从0开始编号,下标为 i(i > 0) 的结点的左右孩子结点及父结点的下标:
左孩子:2i(i>0)
右孩子:2i+1
父节点: (i-1)/2
根据树的父子结点的联系来确定数组下标

void HeapSort(int* a, int n)
{//起始i用n-1是数组的最后一个为n-1,起始i为最后一个元素的父节点for (int i = (n - 1 - 1) / 2;i >= 0;i--){AdjustDwon(a, n, i);}int end = n - 1;//建好大堆,将最大值交换置数组的最后,然后排出最后一个元素,对前n-1的数组进行建堆while(end>0){Swap(&a[0], &a[end]);AdjustDwon(a, end, 0);end--;}
}

对排序的时间复杂度

建堆的时间复杂度:

在堆排序中,首先需要将待排序的序列构建成一个最大堆。构建最大堆的时间复杂度是O(n),其中 n 是待排序序列的长度。这是因为我们只需要对具有父子关系的一半节点进行堆化操作,而这一半节点通常是 n/2。

排序过程的时间复杂度:

堆排序的排序过程包括了 n-1 次交换和堆调整的操作。每次交换涉及到堆顶元素与末尾元素的交换,然后对剩余的 n-1 个元素进行堆调整。堆调整的时间复杂度为O(log n)。因此,排序过程的总时间复杂度为 O((n-1) * log n),约等于O(n log n)。

总体时间复杂度:

将建堆和排序过程的时间复杂度结合起来,堆排序的总体时间复杂度为 O(n + n log n)。在大 O 表示法中,通常会忽略掉低阶项和常数系数,因此可以简化为 O(n log n)。

堆排序的时间复杂度是相对较好的,且具有原地排序的特点。然而,需要注意的是,堆排序在实际应用中可能会因为其不具备稳定性(相同元素的相对位置可能发生变化)和对缓存的不友好等原因而被其他算法替代。

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

时间序列分类算法 极简设计之ROCKET、MiniRocket详解及python实战

前言 时间序列分类任务也是比较常见的任务&#xff0c;根据分类&#xff0c;来判断时间序列的性质&#xff0c;类别等。 其中rocket算法十分另类&#xff0c;看似用的非常简单且暴力的方式&#xff0c;却拿到了不错的效果&#xff0c;以及拥有非常快的推理和训练速度。 后续还有…

Java并发基础:ArrayBlockingQueue全面解析!

内容摘要 ArrayBlockingQueue类是一个高效、线程安全的队列实现&#xff0c;它基于数组&#xff0c;提供了快速的元素访问&#xff0c;并支持多线程间的同步操作&#xff0c;作为有界队列&#xff0c;它能有效防止内存溢出&#xff0c;并通过阻塞机制平衡生产者和消费者的速度…

[职场] 公安管理学就业方向及前景 #媒体#笔记#笔记

公安管理学就业方向及前景 公安管理学是中国普通高等学校本科专业。本专业文理兼收&#xff0c;学制4年&#xff0c;授予法学学士学位。本专业培养掌握马克思主义基本原理&#xff0c;政治坚定&#xff0c;坚持党和国家的路线、方针、政策&#xff0c;具有良好职业素养、科学素…

K210如何下载程序

一、打开资料包里提供的K-Flash程序烧录软件 二、选择串口 三、选择波特率 四、选择In-Chip&#xff0c;烧录到Flash芯片里面&#xff0c;重新上电还会运行程序 五、如果选择In - Memory&#xff0c;这次可以运行&#xff0c;但下次重新上电就不会保持这次的程序了。 六、选择固…

macOS Sonoma 14.3.1(23D60)发布

系统介绍 黑果魏叔2 月 9 日消息&#xff0c;苹果今日向 Mac 电脑用户推送了 macOS 14.3.1 更新&#xff08;内部版本号&#xff1a;23D60&#xff09;&#xff0c;本次更新距离上次发布隔了 17 天。 魏叔 查询苹果官方更新日志&#xff0c;macOS Sonoma 14.3.1 修复内容和 …

LeetCode-第28题-找出字符串中第一个匹配项的下标

1.题目描述 给你两个字符串 haystack 和 needle &#xff0c;请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标&#xff08;下标从 0 开始&#xff09;。如果 needle 不是 haystack 的一部分&#xff0c;则返回 -1 。 2.样例描述 3.思路描述 可以让字符串 …

【JAVA WEB】盒模型

目录 边框 内边距 基础写法 复合写法 外边距 基础写法 复合写法 块级元素的水平居中 弹性布局 设置行内元素的属性 &#xff0c;span 每一个HTML元素就相当于是一个矩形的“盒子” 这个盒子由以下这几个部分构成&#xff1a; 1.边框 border 2.内容 content 3.内边…

写后台接口,前后台数据对接(vue+springboot)

一、怎么写接口&#xff1f;&#xff1f;&#xff1f; 1.Entity&#xff08;定义一堆属性之类的&#xff09; altins>getter和setter方法 2.Controller 3.Service&#xff08;查询出数据&#xff09; 调用了一个方法 4.Mapper 5.回到service&#xff08;返回数据&#x…

2019 年全国职业院校技能大赛高职组 “信息安全管理与评估”赛项任务书(笔记详解)

1. 网络拓扑图 2. IP 地址规划表 3. 设备初始化信息 阶段一 任务 1:网络平台搭建 1、根据网络拓扑图所示,按照 IP 地址参数表,对 DCFW 的名称、各接口IP 地址进行配置。 2、根据网络拓扑图所示,按照 IP 地址参数表,对 DCRS 的名称进行配置,创建 VLAN 并将相应接口划入 …

ChatGPT高效提问—prompt常见用法(续篇七)

ChatGPT高效提问—prompt常见用法&#xff08;续篇七&#xff09; 1.1 零样本、单样本和多样本 ​ ChatGPT拥有令人惊叹的功能和能力&#xff0c;允许用户自由向其提问&#xff0c;无须提供任何具体的示例样本&#xff0c;就可以获得精准的回答。这种特性被称为零样本&#x…

【教3妹学编程-算法题】LCP 30. 魔塔游戏

3妹&#xff1a;2哥&#xff0c;干嘛呢&#xff0c;一个人闷闷不乐的&#xff0c;在看什么呢。 2哥 : 这不快过年了嘛&#xff0c; 想回家过年给我的小侄子买个礼物&#xff0c;结果他张口说想要个ps5. 那玩意我都没有&#xff0c;他还想要。我看看网上有什么好的礼物适合他的。…

vscode开发FPGA(0)--windows平台搭建

一、从官网下载安装VScode Download Visual Studio Code - Mac, Linux, Windows 二、安装配置插件 1. 安装Chinese&#xff08;simplified&#xff09;中文汉化包 2.安装Verilog-HDL/systemVerilog插件(支持verilog语法) 3.配置CTags Support插件(支持代码跳转) 1)在github下…

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之Slider组件

鸿蒙&#xff08;HarmonyOS&#xff09;项目方舟框架&#xff08;ArkUI&#xff09;之Slider组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、Slider组件 滑动条组件&#xff0c;通常用于快速调节设置值&#xff0c;如音量调…

AcWing 1224 交换瓶子(简单图论)

[题目概述] 有 N 个瓶子&#xff0c;编号 1∼N&#xff0c;放在架子上。 比如有 5 个瓶子&#xff1a; 2 1 3 5 4 要求每次拿起 2 个瓶子&#xff0c;交换它们的位置。 经过若干次后&#xff0c;使得瓶子的序号为&#xff1a; 1 2 3 4 5 对于这么简单的情况&#xff0c;显然&a…

[SAP] ABAP代码程序美化器大小写格式化设置

按照ABAP开发的规范&#xff0c;ABAP源代码里推荐将所有的关键字大写&#xff0c;其余ABAP变量小写 我们可以手动修改上述代码大小写规范的问题&#xff0c;但如果代码量很多的情况下&#xff0c;手动确保这个规范(所有的关键字大写&#xff0c;其余ABAP变量小写)有点费事&…

LabVIEW工业监控系统

LabVIEW工业监控系统 介绍了一个基于LabVIEW软件开发的工业监控系统。系统通过虚拟测控技术和先进的数据处理能力&#xff0c;实现对工业过程的高效监控&#xff0c;提升系统的自动化和智能化水平&#xff0c;从而满足现代工业对高效率、高稳定性和低成本的需求。 随着工业自…

TP-LINK今年的年终奖。。

TP-LINK 年终奖 如果说昨天爆料的「浦发银行年终奖&#xff0c;一书抵万金」还稍有争议&#xff08;有些说没发&#xff0c;有些说 3/4/5 折&#xff09;&#xff0c;那今天的 TP-LINK 则是毫无悬念。 据在职的 TP-LINK 技术员工爆料&#xff1a;入职时说好的 16 薪&#xff0c…

Blazor Wasm Gitee 码云登录

目录: OpenID 与 OAuth2 基础知识Blazor wasm Google 登录Blazor wasm Gitee 码云登录Blazor SSR/WASM IDS/OIDC 单点登录授权实例1-建立和配置IDS身份验证服务Blazor SSR/WASM IDS/OIDC 单点登录授权实例2-登录信息组件wasmBlazor SSR/WASM IDS/OIDC 单点登录授权实例3-服务端…

联合体知识点解析

联合体&#xff1a; 联合体也是一种自定义类型&#xff0c; 特点是成员变量公用一块空间。所以也叫共用体。 联合体的性质 先定义一个联合体&#xff1a; 然后我创建一个联合体变量&#xff1a; 现在探究当修改一个成员变量的值时&#xff0c; 其他成员变量的值能否被修改&am…

Python相关的基础模块

Python相关的基础模块 在编写远程控制工具之前&#xff0c;先要介绍用Python编写远程控制工具时所需要的 相关模块&#xff0c;为接下来编写工具打下基础。 1.subprocess模块 subprocess模块的主要作用是执行外部的命令和程序。当我们运行Python的时 候&#xff0c;其实也是在运…