理解堆排序

embedded/2024/12/22 0:44:25/

堆排序(Heapsort)是一种基于堆这种数据结构的排序算法,但在实际实现中,堆通常是用数组来表示的。这种方法充分利用了数组的特性,使得堆的操作更加高效。下面通过详细解释和举例说明来帮助理解这种排序方式。

堆的数组表示

一个堆是一种完全二叉树,可以通过数组方便地表示:

  • 对于一个节点在数组中的索引i:
    • 它的左子节点的索引是 2*i + 1
    • 它的右子节点的索引是 2*i + 2
    • 其父节点的索引是 (i - 1) // 2

堆排序的步骤

  1. 构建初始堆:将无序数组转化为最大堆或最小堆。这个过程称为“建堆”。

  2. 排序

    • 将堆顶元素(最大值或最小值)与数组的最后一个元素交换。
    • 将堆的大小减一,并对新的堆顶元素执行“堆化”操作,恢复堆的性质。
    • 重复上述步骤,直到堆的大小变为1。

举例说明

假设我们有一个无序数组 [4, 10, 3, 5, 1],我们将用堆排序将它排序。

1. 构建初始堆

首先,我们构建最大堆。调整后的堆如下:

         10/  \5    3/ \4   1

数组表示为 [10, 5, 3, 4, 1]

2. 排序过程
  • 第一步:将堆顶元素10与最后一个元素1交换,然后调整堆。

    • 交换后数组变为 [1, 5, 3, 4, 10]
    • 调整堆后数组变为 [5, 4, 3, 1, 10]
  • 第二步:将堆顶元素5与倒数第二个元素1交换,然后调整堆。

    • 交换后数组变为 [1, 4, 3, 5, 10]
    • 调整堆后数组变为 [4, 1, 3, 5, 10]
    • 进一步调整后数组变为 [4, 3, 1, 5, 10]
  • 第三步:将堆顶元素4与倒数第三个元素1交换,然后调整堆。

    • 交换后数组变为 [1, 3, 4, 5, 10]
    • 调整堆后数组变为 [3, 1, 4, 5, 10]
    • 由于此时堆只有两个元素,因此不需要进一步调整。
  • 第四步:将堆顶元素3与倒数第四个元素1交换,然后调整堆。

    • 交换后数组变为 [1, 3, 4, 5, 10]
    • 调整堆后数组变为 [1, 3, 4, 5, 10]
    • 由于此时堆只有一个元素,因此不需要进一步调整。

最终,数组变为 [1, 3, 4, 5, 10],排序完成。

总结

在堆排序的过程中,虽然我们使用了堆这种数据结构,但实际上,所有的操作都是在数组内部进行的。通过交换数组中的元素,我们在数组上模拟了堆的插入、删除和调整操作。这样,我们可以利用数组的连续内存空间和高效的索引访问特点,同时享受堆数据结构带来的排序优势。


http://www.ppmy.cn/embedded/51296.html

相关文章

项目训练营第二天

项目训练营第二天 用户登录逻辑 1、账户名不少于4位 2、密码不少于8位 3、数据库表中能够查询到账户、密码 4、密码查询时用同样加密脱敏处理手段处理后再和数据库中取出字段进行对比,如果账户名未查询到,直接返回null 5、后端设置相应的脱敏后用户的s…

【论文精读】分类扩散模型:重振密度比估计(Revitalizing Density Ratio Estimation)

文章目录 一、文章概览(一)问题的提出(二)文章工作 二、理论背景(一)密度比估计DRE(二)去噪扩散模型 三、方法(一)推导分类和去噪之间的关系(二&a…

四、C#类型转换

在C#中,类型转换是将一个数据类型的值转换为另一个数据类型的过程。 C#中的类型转换可以分为两种:隐式类型转换和显式类型转换(也称为强制类型转换)。 隐式类型转换 隐式转换是不需要编写代码来指定的转换,编译器会…

Transformer中的类别嵌入

类别嵌入 self.class_embedding nn.Parameter(scale * torch.randn(width))这一行代码的作用是在 VisionTransformer 类中创建并初始化一个类别嵌入向量(class embedding vector),用于表示输入序列的类别信息。 详细解释 类别嵌入 在 Tr…

【Qt快速入门(七)】- QListWidget列表框的使用

目录 Qt快速入门(七)- QListWidget列表框的使用QListWidget列表框的使用QListWidget的基本用法项管理1. 插入和删除项2. 查找和排序项信号与槽1. 处理项选择事件2. 处理项双击事件样式设置1. 设置项的字体和颜色2. 设置项的背景颜色3. 自定义项样式扩展功能1. 多选2. 拖放3. …

华为某员工爆料:三年前985本科起薪30万,现在硕士起薪还是30w,感慨互联网行情变化

“曾经的30万年薪,是985本科学历的‘标配’,如今硕士也只值这个价?” 一位华为员工的爆料,揭开了互联网行业薪资变化的冰山一角,也引发了不少人的焦虑:互联网人才“通货膨胀”的时代,真的结束了…

AWS——01篇(AWS入门 以及 AWS之EC2实例及简单实用)AWS

AWS——01篇(AWS入门 以及 AWS之EC2实例及简单实用) 1. 前言 2. 创建AWS账户 3. EC2 3.1 启动 EC2 新实例 3.1.1 入口 3.1.2 设置名称 选择服务 3.1.3 创建密钥对 3.1.4 网络设置——安全组 3.1.4.1 初始设置 3.1.4.2 添加安全组规则(开放新…

打造精致UI界面:字体设计的妙招

字体设计是UI设计的关键模块之一。字体设计是否有效可能直接实现或破坏整个UI界面。那么,界面设计的字体设计有哪些规范呢?如何设计细节字体?本文将解释字体设计规范的可读性、可读性和可用性,并介绍UI界面中的字体设计技巧。 如…