排序算法---堆排序

原创不易,转载请注明出处。欢迎点赞收藏~

堆排序(Heap Sort)是一种基于二叉堆数据结构的排序算法。它将待排序的元素构建成一个最大堆(或最小堆),然后逐步将堆顶元素与堆的最后一个元素交换位置,并重新调整堆,使得剩余未排序部分继续满足堆的性质。通过不断重复这个过程,最终将得到一个有序的序列。

具体步骤如下:
1. 构建初始堆:首先将待排序序列看作是完全二叉树,从最后一个非叶子节点开始,逐个向上调整节点,使得以每个节点为根的子树都满足堆的性质。
2. 排序:将堆顶元素与待排序序列的最后一个元素交换位置,然后将剩下的 n-1 个元素重新调整为堆。重复这个过程,直到堆中只剩下一个元素,即完成排序。

堆排序的关键操作是堆的调整,有两种方式可以实现:
1. 自顶向下调整(Down-Heapify):从根节点开始,不断将根节点与其左右子节点中较大(或较小)的交换,直到满足堆的性质。
2. 自底向上调整(Up-Heapify):从最后一个非叶子节点开始往上逐个调整,将每个节点与其左右子节点中较大(或较小)的交换,直到满足堆的性质。

堆排序的时间复杂度为O(nlogn),其中n是待排序元素的个数。堆的构建过程需要O(n)的时间,每次调整堆的操作需要O(logn)的时间,共需要进行n-1次调整。所以总体时间复杂度是O(nlogn)。

堆排序的空间复杂度为O(1),它是一种原地排序算法,不需要额外的存储空间。

堆排序具有以下特点:

稳定性:堆排序是一种不稳定的排序算法,即相同元素的相对位置可能会发生改变。
适应性:堆排序适用于大规模数据的排序,因为它的时间复杂度不会随数据规模增大而增加,且不需要额外的存储空间。
不适应性:堆排序不适用于小规模数据的排序,因为它的常数因子较大,且堆的构建过程需要较多的比较和交换操作。


需要注意的是,堆排序对于相同元素的排序可能会打乱它们的原始相对顺序,这是由于堆本身的性质所决定的。如果要保持相同元素的相对顺序不变,可以采用稳定的排序算法来代替堆排序。

以下是一个使用C语言实现堆排序的示例代码:

#include <stdio.h>

// 交换两个元素的值
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 调整最大堆,使根节点为最大值
void max_heapify(int arr[], int n, int i)
{
    int largest = i;       // 初始化最大值为根节点
    int left = 2 * i + 1;  // 左子节点索引
    int right = 2 * i + 2; // 右子节点索引

    // 如果左子节点大于根节点,更新最大值为左子节点
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子节点大于当前最大值,更新最大值为右子节点
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大值不是根节点,则交换根节点和最大值
    if (largest != i)
    {
        swap(&arr[i], &arr[largest]);

        // 递归调整交换后的子树
        max_heapify(arr, n, largest);
    }
}

// 堆排序函数
void heap_sort(int arr[], int n)
{
    // 构建最大堆(初始状态)
    for (int i = n / 2 - 1; i >= 0; i--)
        max_heapify(arr, n, i);

    // 逐个将堆顶元素移至末尾,并重新调整堆
    for (int i = n - 1; i > 0; i--)
    {
        // 将堆顶元素(最大值)与当前未排序部分的最后一个元素交换
        swap(&arr[0], &arr[i]);

        // 对剩余元素进行调整,使其满足最大堆性质
        max_heapify(arr, i, 0);
    }
}

int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组:\n");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }

    heap_sort(arr, n);

    printf("\n排序后的数组: \n");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    putchar('\n');

    return 0;
}

这个示例中实现了堆排序算法。代码首先定义了两个辅助函数:swap用于交换两个元素的值,max_heapify用于调整最大堆。

max_heapify函数接收一个数组、堆的大小n和要调整的节点索引i作为参数。该函数首先将最大值初始化为当前节点(根节点),然后比较左子节点和右子节点的值,更新最大值。如果最大值不是根节点,则将其与根节点交换,并递归调用max_heapify来保持堆的性质。

heap_sort函数首先构建最大堆(通过循环调用max_heapify),然后逐个将堆顶元素(最大值)移动到未排序部分的末尾,并重新调整堆。在每次迭代中,通过swap操作将最大值放在数组的末尾,并对剩余元素进行调整,使其满足最大堆的性质。

最后,main函数创建一个包含一些无序元素的数组,并调用heap_sort函数对数组进行排序。排序后,打印出排序后的数组。

请注意,这只是一个简单的堆排序示例,实际应用中可能需要考虑更多的边界情况和错误处理。

运行如上代码,你可以看到以下输出:

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

javaEE - 22( 5000 字 Tomcat 和 HTTP 协议入门 -3)

一&#xff1a;Tomcat 1.1 Tomcat 是什么 谈到 “汤姆猫”, 大家可能更多想到的是大名鼎鼎的这个: 事实上, Java 世界中的 “汤姆猫” 完全不是一回事, 但是同样大名鼎鼎. Tomcat 是一个 HTTP 服务器. 前面我们已经学习了 HTTP 协议, 知道了 HTTP 协议就是 HTTP 客户端和…

Java编程构建高效二手交易平台

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…

物资捐赠管理系统

文章目录 物资捐赠管理系统一、项目演示二、项目介绍三、系统部分功能截图四、部分代码展示五、底部获取项目&#xff08;9.9&#xffe5;带走&#xff09; 物资捐赠管理系统 一、项目演示 爱心捐赠系统 二、项目介绍 基于springboot的爱心捐赠管理系统 开发语言&#xff1a…

APEX开发过程中需要注意的小细节2

开发时遇到首次获取租户号失败的问题 以为是触发顺序问题&#xff0c;所以设置两个动态操作&#xff0c;一个事件是“更改”&#xff0c;另一个是“单击”&#xff0c; 但还是没有解决&#xff0c; 后来终于找到解决方法:在校验前执行取值 果然成功执行&#xff01; 动态查询年…

获取视频帧图片

在实现了minio文件上传的基础上进行操作 一、编写pom <dependency><groupId>org.jcodec</groupId><artifactId>jcodec</artifactId><version>0.2.5</version> </dependency> <dependency><groupId>org.jcodec<…

30岁还一事无成,怎么办?

前些日子&#xff0c;知乎有一个话题&#xff0c;特别火。 原话是&#xff1a;30岁&#xff0c;如果你还没当上管理层&#xff0c;或者在某个领域取得成就&#xff0c;那你一辈子基本也就这样了。 这句话一出&#xff0c;戳中了许多人的软肋&#xff0c;一时间群情哗然。 理由是…

Vue.js2+Cesium1.103.0 十五、绘制视锥,并可实时调整视锥姿态

Vue.js2Cesium1.103.0 十五、绘制视锥&#xff0c;并可实时调整视锥姿态 Demo <template><divid"cesium-container"style"width: 100%; height: 100%;"/> </template><script> /* eslint-disable no-undef */ /* eslint-disable …

【NICN】探索牛客之求阶乘

1.题目描述 递归和非递归分别实现求n的阶乘&#xff08;不考虑溢出的问题&#xff09; 2.代码解题 2.1递归 递归思想&#xff1a; Fac(N) 1*2*3*……*N递归方式实现&#xff1a;1 N < 1 Fac(N)Fac(N-1)*N N > 2 long long Fac(int N) {if(N < 1)return 1;retu…

(每日持续更新)信息系统项目管理(第四版)(高级项目管理)考试重点整理第10章 项目进度管理(四)

博主2023年11月通过了信息系统项目管理的考试&#xff0c;考试过程中发现考试的内容全部是教材中的内容&#xff0c;非常符合我学习的思路&#xff0c;因此博主想通过该平台把自己学习过程中的经验和教材博主认为重要的知识点分享给大家&#xff0c;希望更多的人能够通过考试&a…

力扣hot100 -- 双指针

目录 &#x1f382;移动零 &#x1f319;盛最多水的容器 &#x1f33c;三数之和 &#x1f33c;接雨水 前缀和 辅助数组 双指针 单调栈 &#x1f382;移动零 283. 移动零 - 力扣&#xff08;LeetCode&#xff09; 关于swap #include <iostream> #include <vec…

Get Ready!这些 ALVA 应用即将上线 Vision Pro!

日前&#xff0c;苹果 Vision Pro 正式在美国上市&#xff0c;应用商店首批上线超过 600 款应用程序&#xff0c;出色的显示效果和交互体验&#xff0c;为更多应用提供了全新打开方式。 *图源&#xff1a;Apple 对此&#xff0c;作为全球领先的空间计算技术平台供应商&#xff…

1-3 动手学深度学习v2-线性回归的从零开始实现-笔记

手动创建训练数据集 根据带有噪声的线性模型构造一个人造数据集。我们使用线性模型参数 w [ 2 , − 3.4 ] T \pmb{w} [2,-3.4]^{T} w[2,−3.4]T、 b 4.2 b 4.2 b4.2和噪声项 ϵ \epsilon ϵ生成数据集及其标签&#xff1a; y X w b ϵ \pmb{y} \pmb{Xw}b\epsilon yXw…

Elasticsearch(二)

1、核心概念 1.1、索引&#xff08;Index&#xff09; 一个索引就是一个拥有几分相似特征的文档的集合。比如说&#xff0c;你可以有一个客户数据的索引&#xff0c;另一个产品目录的索引&#xff0c;还有一个订单数据的索引。一个索引由一个名字来标识&#xff08;必须全部是…

【开源】基于JAVA+Vue+SpringBoot的智慧社区业务综合平台

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 业务类型模块2.2 基础业务模块2.3 预约业务模块2.4 反馈管理模块2.5 社区新闻模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 业务类型表3.2.2 基础业务表3.2.3 预约业务表3.2.4 反馈表3.2.5 社区新闻表 四、系统展…

【51单片机】烧写教程:将代码下载到单片机中(图示&解析)

前言 大家好吖&#xff0c;欢迎来到 YY 滴单片机系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过单片机的老铁 这是LCD基本实验中的一部分&#xff0c;完整实验传送门如下&#xff1a;传送门 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是…

[office] excel表格怎么绘制股票的CCI指标- #媒体#学习方法#笔记

excel表格怎么绘制股票的CCI指标? excel表格怎么绘制股票的CCI指标&#xff1f;excel表格中想要绘制一个股票cci指标&#xff0c;该怎么绘制呢&#xff1f;下面我们就来看看详细的教程&#xff0c;需要的朋友可以参考下 CCI指标是一种在股票&#xff0c;贵金属&#xff0c;货…

HARRYPOTTER: FAWKES

攻击机 192.168.223.128 目标机192.168.223.143 主机发现 nmap -sP 192.168.223.0/24 端口扫描 nmap -sV -p- -A 192.168.223.143 开启了21 22 80 2222 9898 五个端口&#xff0c;其中21端口可以匿名FTP登录&#xff0c;好像有点说法,百度搜索一下发现可以用anonymous登录…

力扣热门100题- 10. 正则表达式匹配

力扣热门100题 - 10. 正则表达式匹配 题目描述&#xff1a;示例&#xff1a;提示&#xff1a;解题思路&#xff08;动态规划&#xff09;&#xff1a; 题目链接&#xff1a;10. 正则表达式匹配 题目描述&#xff1a; 给你一个字符串 s 和一个字符规律 p&#xff0c;请你来实现…

【复现】Rebuild管理系统SSRF漏洞_44

目录 一.概述 二 .漏洞影响 三.漏洞复现 1. 漏洞一&#xff1a; 四.修复建议&#xff1a; 五. 搜索语法&#xff1a; 六.免责声明 一.概述 REBUILD&#xff08;简称 RB&#xff09;是一款高度可配置化的 企业管理系统&#xff0c;旨在帮助企业快速完成信息化建设&#x…

【Kubernetes】在k8s1.24及以上版本基于containerd容器运行时测试pod从harbor拉取镜像

基于containerd容器运行时测试pod从harbor拉取镜像 1、安装高版本containerd2、安装docker3、登录harbor上传镜像4、从harbor拉取镜像 1、安装高版本containerd 集群中各个节点都要操作 yum remove containerd.io -y yum install containerd.io-1.6.22* -y cd /etc/containe…