C++ 堆排序

article/2024/2/25 20:55:03

C++ 堆排序

堆排序是一种基于二叉堆数据结构的排序算法,其原理如下:

  1. 构建最大堆:将待排序的数组看作一个完全二叉树,并通过调整节点的位置构建一个最大堆。最大堆满足每个父节点的值都大于或等于其子节点的值。构建最大堆的过程可以从最后一个非叶子节点开始,逐步向前,对每个节点进行下沉操作,使得子树满足最大堆的性质。

  2. 排序过程:构建完成最大堆后,将堆顶元素(即最大值)与数组的最后一个元素交换。然后,将堆的大小减1,再对堆顶元素执行下沉操作,以重新满足最大堆的性质。重复这个过程,直到堆的大小减少到1。最终,得到的数组就是有序的。

堆排序的关键操作是下沉(sink)和上浮(swim):

  • 下沉操作:将某个节点与其子节点中较大的节点交换位置,并递归地对交换后的子节点执行下沉操作,直到满足最大堆的性质。
  • 上浮操作:将某个节点与其父节点比较,如果节点的值大于父节点的值,则交换位置,并递归地对交换后的父节点执行上浮操作,直到满足最大堆的性质。

堆排序的时间复杂度为O(n log n),其中n是待排序数组的长度。构建最大堆的时间复杂度是O(n),排序过程需要进行n次下沉操作,每次下沉操作的时间复杂度是O(log n)。由于堆排序是原地排序算法,不需要额外的辅助空间,因此空间复杂度是O(1)。

需要注意的是,堆排序是不稳定的排序算法,即相等元素的相对顺序可能会发生改变。

#include <iostream>
using namespace std;void heapify(int arr[], int n, int i) {int largest = i;  // 将当前节点设置为最大值int left = 2 * i + 1;  // 左子节点索引int right = 2 * i + 2;  // 右子节点索引// 如果左子节点存在且大于根节点,则更新最大值索引if (left < n && arr[i] < arr[left]) {largest = left;}// 如果右子节点存在且大于根节点或左子节点,则更新最大值索引if (right < n && arr[largest] < arr[right]) {largest = right;}// 如果最大值不是根节点,则交换根节点和最大值,并继续调整堆if (largest != i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}void heapSort(int arr[], int n) {// 构建最大堆(从最后一个非叶子节点开始)for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 逐个将最大值移到数组末尾,并重新调整堆for (int i = n - 1; i > 0; i--) {swap(arr[0], arr[i]);  // 交换根节点和最后一个节点heapify(arr, i, 0);}
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);heapSort(arr, n);cout << "排序后的数组: ";for (int i = 0; i < n; i++) {cout << arr[i] << " ";}return 0;
}


http://www.ngui.cc/article/show-1899203.html

相关文章

猫头虎分享:Win11系统家庭版组策略编辑器怎么打开? Windows11家庭版没有gpedit.msc如何解决?

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

智胜未来,新时代IT技术人风口攻略-第一版(弃稿)

文章目录 抛砖引玉 鸿蒙生态小科普焦虑之下 理想要落到实处校园鼎力 鸿蒙发展不可挡培训入场 机构急于吃红利企业布局 鸿蒙应用规划动智胜未来 技术人风口来临 鸿蒙已经成为行业的焦点&#xff0c;未来的发展潜力无限。作为一名程序员兼UP主&#xff0c;我非常荣幸地接受了邀请…

Android 10.0 锁屏壁纸 LockscreenWallpaper

前言 一、设置壁纸 通过系统设置进行锁屏壁纸和桌面壁纸的设置。 Setting 部分的代码&#xff1a; packages/apps/WallpaperPicker2/src/com/android/wallpaper/module/DefaultWallpaperPersister.java private int setStreamToWallpaperManagerCompat(InputStream inputStre…

算法-3-基本的数据结构

单双链表 1.单链表双链表如何反转 import java.util.ArrayList; import java.util.List;public class Code01_ReverseList {public static class Node {public int value;public Node next;public Node(int data) {value data;}}public static class DoubleNode {public int…

spring boot整合cache使用Ehcache 进行数据缓存

之前的文章 spring boot整合 cache 以redis服务 处理数据缓存 便捷开发 带着大家通过spring boot整合了 cache 缓存 那么 我们就来说说 其他服务的缓存 而spring boot默认的缓存方案就是 cache 用simple模式 spring boot的强大在于它的整合能力 它将其他缓存技术整合 统一了接…

KY141 最大连续子序列

最长连续子序列和&#xff0c;区间DP ti #include<bits/stdc.h>using namespace std;int n, a[10010]; int res1, res2, ans; int dp[10010];int main() {while(cin>>n && n){memset(dp, 0, sizeof dp);bool f 1;for(int i 0; i < n; i ){cin>&g…

【Tauri】(2):使用Tauri应用开发,使用开源的Chatgpt-web应用做前端,使用rust 的candle做后端,本地运行小模型桌面应用

视频演示地址 https://www.bilibili.com/video/BV17j421X7Zc/ 【Tauri】&#xff08;2&#xff09;&#xff1a;使用Tauri应用开发&#xff0c;使用开源的Chatgpt-web应用做前端&#xff0c;使用rust 的candle做后端&#xff0c;本地运行小模型桌面应用 1&#xff0c;做一个免…

政安晨:在Jupyter中【示例演绎】Matplotlib的官方指南(二){Image tutorial}·{Python语言}

咱们接着上一篇&#xff0c;这次咱们讲使用Matplotlib绘制图像的简短尝试。 我的这个系列的上一篇文章在这里&#xff1a; 政安晨&#xff1a;在Jupyter中【示例演绎】Matplotlib的官方指南&#xff08;一&#xff09;{Pyplot tutorial}https://blog.csdn.net/snowdenkeke/ar…

DOCKER 给运行中的容器添加映射端口

方法1 1、获得容器IP 将container_name 换成实际环境中的容器名或者CONTAINER ID docker inspect container_name | grep IPAddress 2、 iptable转发端口 将容器的42309端口映射到docker主机的8001端口 复制代码 代码如下: iptables -t nat -A DOCKER -p tcp --dport 80…

知识图谱 多模态学习 2024 最新综述

知识图谱遇见多模态学习&#xff1a;综述 论文题目&#xff1a;Knowledge Graphs Meet Multi-Modal Learning: A Comprehensive Survey 论文链接&#xff1a;http://arxiv.org/abs/2402.05391 项目地址&#xff1a;https://github.com/zjukg/KG-MM-Survey 备注&#xff1a;55…