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

堆排序(含证明)

引言

前面我们讲过堆的基本操作的实现,现在给定一个int类型的数组,里面存放的数据是无序的,我们如何利用堆的思想来实现数组内数据的升序排列或降序排列呢?

通过前面讲到的堆的实现,我们可以想到,我们再开辟一块空间来模拟堆,将给定数组里的数据一一插入堆中(pushHeap)。这样做可以是可以,但如果是代码量未免有点大,而且还要额外开辟空间。如果是在平时考试时碰到这种题,那实现起来会有点麻烦。

如果能在给定数组上直接调整并减少点代码量就好了,今天我们就来讲讲如何这样实现堆排序。

堆排序主要涉及到两个步骤:1.建堆 2.利用堆的思想排序(具体怎么排序后面会讲)

接下来我们以排升序为例进行讲解。

如何建堆?

以建大堆为例:

如果是在原数组的基础上进行建大堆,通过前面的堆的学习和实现,我们可以通过在原数组进行向上调整法或向下调整法达到目的。

向上调整法建堆

我们以这个数组为例:

int a[7]={30,60,56,80,70,10,15};

db16d8a0dc2a4f67bd271283f8df41c4.png

要将它建成大堆:

514a5e2b44404f2bbccc36f313196c0e.png

从下向上遍历:从数组的第二个元素(下标为1)开始,依次向上遍历到第一个元素(下标为0)。这是因为堆的第一个元素(根节点)在构建过程中不需要进行向上调整。

向上调整:对于遍历到的每个元素(假设当前元素的下标为i),执行以下步骤:

  • 计算当前元素的父节点下标(parent = (i - 1) / 2)。
  • 比较当前元素与其父节点的值。
  • 如果当前元素的值大于其父节点的值,则交换这两个元素的位置。
  • 交换后,将当前元素的下标更新为其父节点的下标,并重复上述比较和交换步骤,直到当前元素的值不大于其父节点的值,或者当前元素成为根节点。
  • 完成建堆:当遍历完所有元素并完成所有必要的向上调整后,整个数组就形成了一个大顶堆。

附上代码:

void swap(dataType* x, dataType* y)
{dataType tmp = *x;*x = *y;*y = tmp;
}void adjustUp(dataType* a, int child)
{assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[child] > a[parent]) {swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else {break;}}
}void heapSort(int* a, int n) {for (int i = 1; i < n; i++) {adjustUp(a, i);}
}

向下调整法建堆

还是以原来的数组为例:

int a[7]={30,60,56,80,70,10,15};

将它建成大堆:

70f74c4107b6498fbc6520eee434163d.png

从最后一个非叶子节点开始,依次向上遍历每个节点(包括根节点)。对于每个节点,执行以下步骤:

  • 将当前节点视为父节点。
  • 比较其父节点与左右子节点的值(如果存在的话)。
  • 如果父节点的值小于左右子节点中的较小值,则交换父节点与较小子节点的值。
  • 将交换后的较小子节点视为新的父节点,重复上述比较和交换步骤,直到父节点的值大于或等于其所有子节点的值,或者父节点成为叶子节点。

当所有节点都按照上述步骤调整完毕后,整个数组就形成了一个大顶堆。

这里有一个问题,如何算最后一个出非叶子节点的下标呢?

在一个堆中,最后一个叶子节点的下标是n-1,那它父节点的下标就是(n-1-1)/2也就是(n-2)/2。

附上代码:

void swap(dataType* x, dataType* y)
{dataType tmp = *x;*x = *y;*y = tmp;
}
int getMax(dataType* a, int x, int y)
{if (a[x] > a[y]){return x;}else {return y;}
}
void adjustDown(dataType* a, int parent, int size)
{assert(a);while (parent < size){int lChild = 2 * parent + 1, rChild = 2 * parent + 2, swapChild;if (rChild < size) {swapChild = getMax(a, lChild, rChild);}else {swapChild = lChild;}if (swapChild < size && a[parent] < a[swapChild]) {swap(&a[parent], &a[swapChild]);parent = swapChild;}else {break;}}
}
void heapSort(int* a, int n) {//向下调整法for (int i = (n - 2)/2; i >= 0; i--) {adjustDown(a, i, n);}}

时间复杂度

向上调整法建堆

93e52c43bd69448a9efdfc7292ec5f93.jpg

 向下调整法建堆

8930ba646803479f84f7ff66f4d89109.png

总结

对比之下,向下调整法建堆的时间复杂度更低,所以我们更推荐用向下调整法建堆。

一个误区:排升序就是直接将原来无序的数组构建成小堆就可以了

说到建堆,无非就两种:要么建大顶堆,要么建小顶堆。但如果是排升序,很多人可能第一反应是直接建小顶堆就可以了。但是这样真的合适吗?我们以这个数组为例:

int a[5]={30,60,56,70,10};

e58f378a7f574d8cb603c35c7e37db64.png

 把它建成小顶堆会是这样:

099b6ba6382542d48dc376105ea8e18c.png

 对应的数组就是这样了:int a[5]={10,30,56,70,60};

我们发现这样调整后,数组里面的数据并不是完全按照升序排列的。为什么会这样呢?

我们需要知道,在小堆中,堆顶元素确实是最小的。但是,这并不意味着从堆顶到堆尾的所有元素都按升序排列。小堆的结构只保证了从根节点到每个叶子节点的路径上,元素是递增的。然而,不同路径上的元素之间并没有这样的保证。

所以,直接将原来无序的数组构建成小堆是不可行的办法。

排升序建大堆,排降序建小堆

那我们该怎么办呢?

答案是:排升序建大堆,排降序建小堆。

竟然跟我们最初的想法背道而驰,接下来我会讲解一下为什么要这么做以及具体如何实现。

我们以这个数组为例:

int a[5]={4, 10, 3, 5, 1}

具体步骤

1.我们先把将它建成大堆:

int a[5]={10,5,3,4,10}; 

6c8ad0247139419c86865056b7ebad55.png

2.交换堆顶元素与末尾元素:将堆顶元素(当前最大值)与序列末尾元素交换位置。

b7b48cdc67d74159afbe58cb02013d45.png

这一步骤将最大值“沉”到底部,同时保证了剩余元素组成的子序列仍满足堆的性质。

cfac0d24537541be837e6ec964f63d1c.png

3.调整剩余元素:将交换后的剩余元素(除去已排序的堆顶元素)重新调整为一个堆。

由于堆顶元素已被移到末尾,此时需要对剩余元素重新执行向下调整操作,使得新的堆顶元素成为剩余元素中的最大值。

39b3eafe4baa4326a0016302bdb1dfdc.png

 4.重复交换与调整:重复步骤2和步骤3,每次都将当前堆顶元素(即剩余部分的最大值)与末尾元素交换,并对剩余元素重新调整为堆。

53b9bdede498458a8ffed136970aeab9.png

         ①                          ②                         ③

 

0a79bc3a06e344dc84ef06fb4e22c601.png   ④                           ⑤                        ⑥

随着每一次交换和调整,有序序列逐渐扩大,堆的大小逐渐减小。

5.终止条件:当堆的大小减小到1时,整个序列已经有序,堆排序过程结束。

0577ca2b744048fcaf7619f587293fac.png

代码

void swap(dataType* x, dataType* y)
{dataType tmp = *x;*x = *y;*y = tmp;
}
int getMax(dataType* a, int x, int y)
{if (a[x] > a[y]){return x;}else {return y;}
}
void adjustDown(dataType* a, int parent, int size)
{assert(a);while (parent < size){int lChild = 2 * parent + 1, rChild = 2 * parent + 2, swapChild;if (rChild < size) {swapChild = getMax(a, lChild, rChild);}else {swapChild = lChild;}if (swapChild < size && a[parent] < a[swapChild]) {swap(&a[parent], &a[swapChild]);parent = swapChild;}else {break;}}
}
void heapSort(int* a, int n) {//向下调整法for (int i = (n - 2)/2; i >= 0; i--) {adjustDown(a, i, n);}int cnt = n - 1;while (cnt) {swap(&a[0], &a[cnt]);adjustDown(a, 0, cnt);--cnt;}}

时间复杂度

前面我们知道,通过向下调整法构建初始堆的时间复杂度为O(n),因为需要对n个元素进行一次向下调整操作。

交换堆顶元素与末尾元素并重新调整堆的过程需要重复n-1次,每次调整的时间复杂度为O(log n)。

因此,总的时间复杂度为O(n log n)。

如果排升序建小堆

在堆排序中,如果目标是进行升序排序,通常我们会选择构建大顶堆,而不是小顶堆。这是因为大顶堆的堆顶元素是最大的,通过不断地将堆顶元素与末尾元素交换并调整堆,可以逐步将序列排序为升序。

然而,如果尝试使用小顶堆来进行升序排序,步骤和弊端如下:

具体步骤

1.建堆:给定一个无序数组int a[5]={4, 10, 3, 5, 1},通过向下调整法将其构建为小顶堆int a[5]={1, 3, 4,5,10};

        1
       /  \
     3    4
     / \
   5   10

 

2.交换与调整:将小顶堆的堆顶元素(当前最小值)与数组末尾元素交换位置。

堆顶元素(1)与数组末尾元素(10)交换:      

      10
      /  \
    3    4
    / \
  5    1
由于交换后的堆顶元素可能不再是最小值,因此需要对剩余元素重新调整为小顶堆。

对应的数组表示变为:[10, 3, 4, 5, 1],此时,1已经被放到了数组最后的位置,不再参与后续堆化。

但是注意了,剩余元素[10, 3, 4, 5]需要重新调整为小顶堆。但是,不能直接通过下沉操作将3放到堆顶,因为这里的adjustDown函数是从堆顶开始与较大的子节点交换,直到找到合适的位置。在这个情况下,堆顶是10,它是当前堆中的最大值,下沉操作会将它与孩子几点钟较大的那一个孩子节点交换,也就是4,并不能把3交换上去。

正确的重新堆化过程:实际上,我们需要从最后一个非叶子节点开始(在这个例子中是4),向上逐个节点进行堆化,确保每个子树都满足小顶堆的性质。
然后,我们再将根节点(10)与其子节点中较小的一个进行交换,直到整个堆满足小顶堆的性质。
这个过程比简单地下沉操作要复杂得多,因为它可能涉及到多次交换和比较。

 

3.重复步骤:重复步骤2,每次都将新的堆顶元素(当前最小值)与数组末尾元素交换,并重新调整剩余元素为小顶堆。

弊端(与大顶堆相比)

一、效率低下

  • 小顶堆:
  1. 每次交换到末尾的是当前最小值。
  2. 需要对整个堆进行重新调整以得到下一个最小值。
  3. 迭代过程中每次都需要进行调整,导致整体效率低下。
  • 大顶堆:
  1. 每次交换到末尾的是当前最大值。
  2. 剩余元素自然形成新的堆,只需对堆顶元素进行向下调整。
  3. 每次迭代的时间复杂度相对较低。

二、稳定性问题

  • 小顶堆升序排序时,每次交换最小值可能破坏相同元素的相对顺序,稳定性问题更突出。

三、逻辑复杂性

  • 小顶堆用于升序排序反直觉。
  • 升序排序目标为从小到大排列,大顶堆堆顶为当前最大值,更符合需求。
  • 小顶堆需每次交换后进行复杂调整操作。

 

ps:在第一次学习数据结构的时候,我并没有学过堆排序。这篇博客也是本人到目前为止写的最心累的一篇博客!其实如果掌握好了前面堆的实现的内容,堆排序理解和实现起来并不难。所以前面的内容一定要理解到位!

 

 

 

 

相关文章:

堆排序(含证明)

引言 前面我们讲过堆的基本操作的实现&#xff0c;现在给定一个int类型的数组&#xff0c;里面存放的数据是无序的&#xff0c;我们如何利用堆的思想来实现数组内数据的升序排列或降序排列呢&#xff1f; 通过前面讲到的堆的实现&#xff0c;我们可以想到&#xff0c;我们再开…...

蓝桥杯模拟题不知名题目

题目:p是一个质数&#xff0c;但p是n的约数。将p称为是n的质因数。求2024最大质因数。 #include<iostream> #include<algorithm> using namespace std; bool fun(int x) {for(int i 2 ; i * i < x ; i){if(x % i 0)return false;}return true; } int main() …...

C#中的工厂模式

在C#中&#xff0c;工厂模式&#xff08;Factory Pattern&#xff09; 是一种常见的设计模式&#xff0c;它属于创建型模式&#xff0c;主要用于定义一个用于创建对象的接口&#xff0c;让子类决定实例化哪一个类。通过使用工厂模式&#xff0c;客户端代码不需要直接实例化具体…...

深度学习与持续学习:人工智能的未来与研究方向

文章目录 1. 持续学习与深度学习1.1 深度学习的局限1.2 持续学习的定义 2. 目标与心智2.1 奖励假说2.2 心智的构成 3. 对研究方法的建议3.1 日常写作记录3.2 中立对待流行趋势 1. 持续学习与深度学习 1.1 深度学习的局限 深度学习注重“瞬时学习”&#xff0c;如ChatGPT虽在语…...

OGRE 3D----4. OGRE和QML共享opengl上下文

在现代图形应用开发中,OGRE(Object-Oriented Graphics Rendering Engine)和QML(Qt Modeling Language)都是非常流行的工具。OGRE提供了强大的3D渲染能力,而QML则用于构建灵活的用户界面。在某些应用场景中,我们需要在同一个应用程序中同时使用OGRE和QML,并且共享OpenGL…...

【Umi】常用配置

具体见&#xff1a;alias 1. 基础配置 1)配置别名alias 2)配置sourcemap devtool 配置项 3)添加hash 4)图片转base64 inlineLimit 配置项 5)设置JS压缩方式 jsMinifier (webpack) 、jsMinifierOptions 配置项 6)设置umi插件 plugins 配置项 7)设置打包后资源导入的路…...

Windows加固脚本

echo off REM 清屏 cls title 安全策略设置批处理 color f0 echo **************************************** echo write by afei echo https://www.jianshu.com/u/ea4c85fbe8c7 echo **************************************** pause cls color 3f echo ********************…...

玩游戏常常出现vc++runtime library error R6025 这是什么意思,该怎么解决?

当玩游戏时常常出现“vc runtime library error R6025”错误&#xff0c;这通常表明微软C开发运行库组件存在问题。以下是对该错误及其解决方法的详细解释&#xff1a; 错误含义 “vc runtime library error R6025”是一个与Visual C运行时库相关的错误&#xff0c;该错误表明…...

AGX orin下电控制

AGX orin下电主要有两种&#xff0c;一种通过软件控制下电&#xff0c;另一种通过按键强制关机。下电流程和电脑关机流程类似。 AGX orin核心板与扩展板 AGX orin核心板由英伟达生产&#xff0c;不提供原理图&#xff0c;通过下图所示连接器与扩展板连接。 AGX orin扩展板&am…...

flutter 报错 error: unable to find git in your path.

项目issue&#xff1a;WIndows: "Unable to find git in your PATH." if terminal is not in admin mode Issue #123995 flutter/flutter 解决办法&#xff0c; 方法一&#xff1a;每次想要运行flutter的时候以管理员方式运行&#xff0c;比如以管理方式运行vsco…...

芯科科技率先支持Matter 1.4,推动智能家居迈向新高度

Matter 1.4引入核心增强功能、支持新设备类型&#xff0c;持续推进智能家居互联互通 近日&#xff0c;连接标准联盟&#xff08;Connectivity Standard Alliance&#xff0c;CSA&#xff09;发布了Matter 1.4标准版本。作为连接标准联盟的重要成员之一&#xff0c;以及Matter标…...

C语言数据相关知识:静态数据、越界与溢出

1、静态数组 在 C 语言中&#xff0c;数组一旦被定义后&#xff0c;占用的内存空间就是固定的&#xff0c;容量就是不可改变的&#xff0c;既不能在任何位置插入元素&#xff0c;也不能在任何位置删除元素&#xff0c;只能读取和修改元素&#xff0c;我们将这样的数组称为静态…...

文本分析之余弦相似度

余弦相似度(Cosine Similarity)是一种用于衡量两个非零向量之间相似度的指标,尤其常用于文本分析和自然语言处理领域。其核心思想是通过计算两个向量的夹角余弦值来评估它们的相似性。具体而言,余弦相似度的值范围从-1到1,其中1表示两个向量完全相同,0表示它们之间没有相…...

【VUE3】【Naive UI】<n-button> 标签

【VUE3】【Naive UI】&#xff1c;n-button&#xff1e; 标签 **type**- 定义按钮的类型&#xff0c;这会影响按钮的颜色和样式。**size**- 设置按钮的大小。**disabled**- 布尔值&#xff0c;控制按钮是否处于禁用状态。**loading**- 布尔值&#xff0c;表示按钮是否处于加载状…...

css使盒子在屏幕的地点固定

在 CSS 中&#xff0c;要将一个元素固定在页面的某个位置&#xff0c;可以使用 position: fixed 属性。以下是详细的代码示例和中文解释&#xff1a; <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta n…...

Transformers快速入门代码解析(六):注意力机制——Transformer Encoder:执行顺序解析

Transformer Encoder&#xff1a;执行顺序解析 引言执行顺序解析1. 设置模型检查点和分词器2. 输入预处理操作说明&#xff1a; 3. 加载模型配置configconfig 包含的主要参数常见配置&#xff08;BERT-base&#xff09; 4. 初始化 TransformerEncoder5. Transformer Encoder 的…...

图像小波去噪与总变分去噪详解与Python实现

目录 图像小波去噪与总变分去噪详解与实现1. 基础概念1.1 噪声类型及去噪问题定义1.2 小波去噪算法基础1.3 总变分去噪算法基础2. 小波去噪算法2.1 理论介绍2.2 Python实现及代码详解2.3 案例分析3. 总变分去噪算法3.1 理论介绍3.2 Python实现及代码详解3.3 案例分析4. 两种算法…...

【深度学习基础】预备知识 | 微积分

【作者主页】Francek Chen 【专栏介绍】 ⌈ ⌈ ⌈PyTorch深度学习 ⌋ ⌋ ⌋ 深度学习 (DL, Deep Learning) 特指基于深层神经网络模型和方法的机器学习。它是在统计机器学习、人工神经网络等算法模型基础上&#xff0c;结合当代大数据和大算力的发展而发展出来的。深度学习最重…...

CTF-PWN glibc源码阅读[1]: 寻找libc中堆结构的定义(2.31-0ubuntu9.16)

源代码在这里下载 来到malloc/malloc.c 在980行发现这段代码 // 定义最大 mmap 值为 -4 #define M_MMAP_MAX -4// 如果没有定义 DEFAULT_MMAP_MAX&#xff0c;则将其定义为 65536 #ifndef DEFAULT_MMAP_MAX #define DEFAULT_MMAP_MAX (65536) #endif// 引…...

宏集eXware物联网网关在水务管理系统上的应用

一、前言 水务管理系统涵盖了对城市水网、供水、排水、污水处理等多个环节的监控与管理。随着物联网&#xff08;IoT&#xff09;技术的快速发展&#xff0c;物联网网关逐渐成为水务管理系统中的关键组成部分。 宏集物联网网关以其高效的数据采集、传输和管理功能&#xff0c…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

WEB3全栈开发——面试专业技能点P7前端与链上集成

一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染&#xff08;SSR&#xff09;与静态网站生成&#xff08;SSG&#xff09; 框架&#xff0c;由 Vercel 开发。它简化了构建生产级 React 应用的过程&#xff0c;并内置了很多特性&#xff1a; ✅ 文件系…...

《信号与系统》第 6 章 信号与系统的时域和频域特性

目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...

leetcode_69.x的平方根

题目如下 &#xff1a; 看到题 &#xff0c;我们最原始的想法就是暴力解决: for(long long i 0;i<INT_MAX;i){if(i*ix){return i;}else if((i*i>x)&&((i-1)*(i-1)<x)){return i-1;}}我们直接开始遍历&#xff0c;我们是整数的平方根&#xff0c;所以我们分两…...

欢乐熊大话蓝牙知识17:多连接 BLE 怎么设计服务不会乱?分层思维来救场!

多连接 BLE 怎么设计服务不会乱&#xff1f;分层思维来救场&#xff01; 作者按&#xff1a; 你是不是也遇到过 BLE 多连接时&#xff0c;调试现场像网吧“掉线风暴”&#xff1f; 温度传感器连上了&#xff0c;心率带丢了&#xff1b;一边 OTA 更新&#xff0c;一边通知卡壳。…...