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

C语言堆排序

 

堆排序(Heapsort)是一种在时间复杂度上达到了最优的基于比较的排序算法。堆排序算法是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。

堆排序的基本思想是:

  1. 首先将待排序的序列构造成一个大顶堆(或小顶堆)。
  2. 此时,整个序列的最大值(或最小值)就是堆顶的根节点。
  3. 将其与末尾元素进行交换,此时末尾就为最大值(或最小值)。
  4. 然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值(或次大值)。
  5. 如此反复执行,便能得到一个有序序列了。

堆排序的时间复杂度是O(n log n)。

#include <stdio.h>  // 将以k为根的子树调整为最大堆  
void heapify(int arr[], int n, int k) {  int largest = k;  // 初始化根节点最大  int left = 2 * k + 1;  // 左子节点  int right = 2 * k + 2;  // 右子节点  // 如果左子节点比根节点大,则更新最大节点  if (left < n && arr[left] > arr[largest]) {  largest = left;  }  // 如果右子节点比最大节点大,则更新最大节点  if (right < n && arr[right] > arr[largest]) {  largest = right;  }  // 如果最大节点不是根节点,则交换根节点和最大节点,并继续调整子树  if (largest != k) {  int temp = arr[k];  arr[k] = arr[largest];  arr[largest] = temp;  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--) {  int temp = arr[0];  arr[0] = arr[i];  arr[i] = temp;  heapify(arr, i, 0);  }  
}  int main() {  int arr[] = {10, 7, 8, 9, 1, 5};  int n = sizeof(arr) / sizeof(arr[0]);  printf("Original array: ");  for (int i = 0; i < n; i++) {  printf("%d ", arr[i]);  }  printf("\n");  heapSort(arr, n);  printf("Sorted array: ");  for (int i = 0; i < n; i++) {  printf("%d ", arr[i]);  }  printf("\n");  return 0;  
}

该代码中,heapify函数将以k为根的子树调整为最大堆,heapSort函数则先构建最大堆,然后从堆顶开始取出元素并重新调整堆,最终得到排序后的数组。

相关文章:

C语言堆排序

堆排序&#xff08;Heapsort&#xff09;是一种在时间复杂度上达到了最优的基于比较的排序算法。堆排序算法是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构&#xff0c;并同时满足堆积的性质&#xff1a;即子节点的键值或索引总是小于&#xff0…...

【学习笔记】CF573E Bear and Bowling

感觉贪心的做法比较自然&#x1f914;&#xff0c;推荐 这篇博客 非常经典牛逼的贪心思路&#xff1a; 考虑每次加入一个数&#xff0c;位置 i i i的贡献为 V i k i a i b i V_ik_i\times a_ib_i Vi​ki​ai​bi​&#xff0c;其中 k i k_i ki​表示 i i i以前被选的位置的…...

函数扩展之——内存函数

前言&#xff1a;小伙伴们又见面啦。 本篇文章&#xff0c;我们将讲解C语言中比较重要且常用的内存函数&#xff0c;并尝试模拟实现它们的功能。 让我们一起来学习叭。 目录 一.什么是内存函数 二.内存函数有哪些 1.memcpy &#xff08;1&#xff09;库函数memcpy &…...

【在线机器学习】River对流数据进行机器学习

River是一个用于在线机器学习的Python库。它旨在成为对流数据进行机器学习的最用户友好的库。River是crme和scikit-multiflow合并的结果。 https://github.com/online-ml/river 举个简单示例&#xff0c;将训练逻辑回归来对网站网络钓鱼数据集进行分类。下面介绍了数据集中的…...

第 4 章 串(串的块链存储实现)

1. 背景说明 该实现和链表的实现极为相似&#xff0c;只是将链接的内存拆分为具体的大小的块。 2. 示例代码 1). status.h /* DataStructure 预定义常量和类型头文件 */#ifndef STATUS_H #define STATUS_H#define CHECK_NULL(pointer) if (!(pointer)) { \printf("FuncN…...

Element表格之表头合并、单元格合并

一、合并表头 el-table配置 :header-cell-style"headFirst"headFirst({ row, colunm, rowIndex, columnIndex }) {let base { background-color: rgba(67, 137, 249, 0.3), color: #333, text-align: center };//这里为了是将第一列的表头隐藏&#xff0c;就形成了合…...

go学习-JS的encodeURIComponent转go

背景 encodeURIComponent() 函数通过将特定字符的每个实例替换成代表字符的 UTF-8 编码的一个、两个、三个或四个转义序列来编码 URI&#xff08;只有由两个“代理”字符组成的字符会被编码为四个转义序列&#xff09;。 与 encodeURI() 相比&#xff0c;此函数会编码更多的字…...

MySQL索引、事务与存储引擎

索引 事务 存储引擎 一、索引1.1 索引的概念1.2 索引的实现原理1.2 索引的作用1.3 创建索引的依据1.4 索引的分类和创建1.4.1 普通索引 index1.4.2 唯一索引 unique1.4.3 主键索引 primary key1.4.4 组合索引&#xff08;单列索引与多列索引&#xff09;1.4.5 全文索引 fulltex…...

【Spring面试】八、事务相关

文章目录 Q1、事务的四大特性是什么&#xff1f;Q2、Spring支持的事务管理类型有哪些&#xff1f;Spring事务实现方式有哪些&#xff1f;Q3、说一下Spring的事务传播行为Q4、说一下Spring的事务隔离Q5、Spring事务的实现原理Q6、Spring事务传播行为的实现原理是什么&#xff1f…...

Windows平台Qt6中UTF8与GBK文本编码互相转换、理解文本编码本质

快速答案 UTF8转GBK QString utf8_str"中UTF文"; std::string gbk_str(utf8_str.toLocal8Bit().data());GBK转UTF8 std::string gbk_str_given_by_somewhere"中GBK文"; QString utf8_strQString::fromLocal8Bit(gbk_str_given_by_somewhere.data());正文…...

【探索Linux】—— 强大的命令行工具 P.9(进程地址空间)

阅读导航 前言一、内存空间分布二、什么是进程地址空间1. 概念2. 进程地址空间的组成 三、进程地址空间的设计原理1. 基本原理2. 虚拟地址空间 概念 大小和范围 作用 虚拟地址空间的优点 3. 页表 四、为什么要有地址空间五、总结温馨提示 前言 前面我们讲了C语言的基础知识&am…...

ESP32主板-MoonESP32

产品简介 Moon-ESP32主板&#xff0c;一款以双核芯片ESP32-E为主芯片的主控板&#xff0c;支持WiFi和蓝牙双模通信&#xff0c;低功耗&#xff0c;板载LED指示灯&#xff0c;引出所有IO端口&#xff0c;并提供多个I2C端口、SPI端口、串行端口&#xff0c;方便连接&#xff0c;…...

Python 图片处理笔记

import numpy as np import cv2 import os import matplotlib.pyplot as plt# 去除黑边框 def remove_the_blackborder(image):image cv2.imread(image) #读取图片img cv2.medianBlur(image, 5) #中值滤波&#xff0c;去除黑色边际中可能含有的噪声干扰#medianBlur( Inp…...

SpringCloud Ribbon--负载均衡 原理及应用实例

&#x1f600;前言 本篇博文是关于SpringCloud Ribbon的基本介绍&#xff0c;希望你能够喜欢 &#x1f3e0;个人主页&#xff1a;晨犀主页 &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是晨犀&#xff0c;希望我的文章可以帮助到大家&#xff0c;您的满意是我的动力…...

Redis的介绍以及简单使用

Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的内存数据存储系统&#xff0c;它以键值对的形式将数据存在内存中&#xff0c;并提供灵活、高性能的数据访问方式。Redis具有高速读写能力和丰富的数据结构支持&#xff0c;可以广泛应用于缓存、消息队列、实…...

ad18学习笔记十二:如何把同属性的元器件全部高亮?

1、先选择需要修改的器件的其中一个。 2、右键find similar objects&#xff0c;然后在弹出的对话框中&#xff0c;将要修改的属性后的any改为same 3、像这样勾选的话&#xff0c;能把同属性的元器件选中&#xff0c;其他器件颜色不变 注意了&#xff0c;如果这个时候&#xff…...

SpringSecurity 核心过滤器——SecurityContextPersistenceFilter

文章目录 前言过滤器介绍用户信息的存储获取用户信息存储用户信息获取用户信息 处理逻辑总结 前言 SecurityContextHolder&#xff0c;这个是一个非常基础的对象&#xff0c;存储了当前应用的上下文SecurityContext&#xff0c;而在SecurityContext可以获取Authentication对象…...

反转单链表

思路图1&#xff1a; 代码&#xff1a; struct ListNode* reverseList(struct ListNode* head){if(headNULL)//当head是空链表时 {return head; }struct ListNode* n1NULL;struct ListNode* n2head;struct ListNode* n3head->next;if(head->nextNULL)//当链表只有一个节…...

加速新药问世,药企如何利用云+网的优势?

随着计算能力的不断提高和人工智能技术的迅速发展&#xff0c;药物研发领域正迎来一场革命。云端强大的智能算法正成为药物研发企业的得力助手&#xff0c;推动着药物的精确设计和固相筛选。这使得药物设计、固相筛选以及药物制剂开发的时间大幅缩短&#xff0c;有望加速新药物…...

C++中string对象之间比较、char*之间比较

#include <cstring> //char* 使用strcmp #include <string> //string 使用compare #include <iostream> using namespace std; int main() {string stringStr1 "42";string stringStr2 "42";string stringStr3 "213";cout …...

总担心家人生病?心理学教你摆脱 “灾难化思维”

父母晚回半小时&#xff0c;孩子轻微咳嗽&#xff0c;伴侣说头晕…… 你是不是瞬间脑补出无数可怕画面&#xff0c;越想越慌&#xff0c;直到拨通电话才安心&#xff1f;这不是矫情&#xff0c;是灾难化思维在作祟。一、为什么总担心家人生病&#xff1f;3个深层根源对失去的恐…...

英语体育比赛口语

一、看比赛1. 邀约看球中文英文今晚有比赛&#xff0c;一起看吗&#xff1f;Theres a game tonight. Want to watch together?你看了昨晚的比赛吗&#xff1f;Did you watch the game last night?决赛什么时候&#xff1f;When is the final?我们去酒吧看球吧&#xff01;Le…...

iStoreOS软路由结合Cpolar内网穿透:打造稳定高效的居家远程办公网络

1. 为什么你需要iStoreOS软路由Cpolar组合&#xff1f; 最近两年远程办公越来越普遍&#xff0c;但很多朋友都遇到过这样的困扰&#xff1a;公司电脑里的文件急着要用&#xff0c;跑回办公室又太麻烦&#xff1b;出差在外需要调取内网资料&#xff0c;VPN连接却卡成幻灯片。我自…...

FPGA实战避坑:手把手教你用Verilog搞定跨时钟域信号传输(附同步/异步FIFO完整代码)

FPGA实战避坑&#xff1a;手把手教你用Verilog搞定跨时钟域信号传输 第一次在FPGA项目里遇到跨时钟域问题&#xff0c;我盯着屏幕上那些随机跳变的数据波形&#xff0c;整整三天没想明白问题出在哪。当时我正在做一个工业传感器数据采集系统&#xff0c;处理器接口跑在100MHz&a…...

电路原理与情感关系的电子工程解读

电子工程视角下的电路与人生哲学1. 电路元件与情感关系的类比分析1.1 信号放大器与初恋心理初恋阶段的心理状态类似于简单的信号放大器系统。在这个模型中&#xff0c;情感输入信号被高度放大&#xff0c;微小的快乐信号能产生极大的幸福感输出&#xff0c;同样微小的伤害信号也…...

【教程4>第12章>第3节】基于FPGA的图像缩放实现2

编写中........................

Pixel Dream Workshop详细步骤:日志系统集成与渲染异常诊断方法

Pixel Dream Workshop详细步骤&#xff1a;日志系统集成与渲染异常诊断方法 1. 像素幻梦创意工坊简介 Pixel Dream Workshop&#xff08;像素幻梦创意工坊&#xff09;是一款基于FLUX.1-dev扩散模型的下一代像素艺术生成工具。它采用明亮的16-bit像素风格界面设计&#xff0c…...

戴森电池管理系统开源固件技术指南:从原理到实践的全面解析

戴森电池管理系统开源固件技术指南&#xff1a;从原理到实践的全面解析 【免费下载链接】FU-Dyson-BMS (Unofficial) Firmware Upgrade for Dyson V6/V7 Vacuum Battery Management System 项目地址: https://gitcode.com/gh_mirrors/fu/FU-Dyson-BMS 第一部分&#xff…...

Wan2.2-I2V-A14B前端面试题实践:用AI视频生成功能丰富个人项目经验

Wan2.2-I2V-A14B前端面试题实践&#xff1a;用AI视频生成功能丰富个人项目经验 1. 为什么前端开发者需要关注AI视频生成 最近两年&#xff0c;前端技术栈的边界正在快速扩展。传统意义上的切图写页面已经不能满足企业对前端工程师的期望&#xff0c;越来越多的团队希望开发者…...

深度解析:智能体认知动力学

引言&#xff1a;智能体认知的变革在人工智能从 "大炼模型" 转向 "大用模型" 的关键时期&#xff0c;张家林的《智能体认知动力学导论&#xff1a;从生成式控制到拓扑几何求解》&#xff08;2026 年版&#xff09;如同一颗投入平静湖面的巨石&#xff0c;激…...