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

考研要求掌握的C语言程度(堆排序)1

含义 

堆排序就是把数组的内容在心中建立为大根堆,然后每次循环把根顶和没交换过的根末进行调换,再次建立大根堆的过程

建树的几个公式

一个数组有n个元素

最后一个父亲节点是n/2-1;

假如父亲节点在数组的下标为a

那么左孩子节点在数组下标为2*a+1,右孩子节点在数组下标为2*a+2

大根堆在心里建树的要点

父亲节点必须大于孩子节点,孩子节点大小位置无影响

【注】数组界限问题,以及传参问题

核心代码

//其实没有树,只不过是我们在心里根据数组层次建树来构建大根堆调整数组的排列顺序
//注意我这里的len是数组的长度,注意一下长度和数组下标间的关系
void AdjustDown(int nums[],int pos,int len)
{int dad = pos;int son = 2*dad+1;//左孩子在数组下标while(son < len){if(son+1<len && nums[son]<nums[son+1]){son++;//挑选出左右孩子最大的,只需把son+1变为右孩子下标}if(nums[son]>nums[dad])//只能父亲大于孩子{swap(nums[son],nums[dad]);//交换数据dad =son;//把当前孩子作为父亲,重新循环son = 2*dad+1;}else{break;}}
}
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
//数组
int nums[]={3,87,2,93,78,56,61,38,12,40};
void init_rand(int nums[],int len)
{srand(time(NULL));for(int i=0;i<len;++i){nums[i]=rand()%100+1;//(1,100)}
}
//交换数据
void swap(int &a,int&b)
{int tmp = a;a=b;b=tmp;
}
void print(int nums[],int len)
{for(int i = 0;i<len ;i++ ){printf("%d ",nums[i]);}printf("\n");
}//其实没有树,只不过是我们在心里根据数组层次建树来构建大根堆调整数组的排列顺序
void AdjustDown(int nums[],int pos,int len)
{int dad = pos;int son = 2*dad+1;//左孩子在数组下标while(son < len){if(son+1<len && nums[son]<nums[son+1]){son++;//挑选出左右孩子最大的,只需把son+1变为右孩子下标}if(nums[son]>nums[dad])//只能父亲大于孩子{swap(nums[son],nums[dad]);//交换数据dad =son;//把当前孩子作为父亲,重新循环son = 2*dad+1;}else{break;}}
}//待排序数组,待排序数组的长度
void heap_sort(int nums[],int len)
{int i;//建立大根堆//从最后一个父亲元素开始for(i=len/2-1;i>=0;--i){//调整没个父亲节点为大根堆//数组,父亲节点所在数组的下标,数组长度AdjustDown(nums,i,len);}//建立大根堆之后,有序的数据是在我们内心中建的树,而不是数组,因此我们还需要把他修改为数组中swap(nums[0],nums[len-1]);//先交换树根和最后一个节点的数据(我这里的len代表长度)// print(nums,len);//接着再次进入建立大根堆,换数据的循环中,直到数组有序for(i=len-1;i>0;i--){AdjustDown(nums,0,i);//每次从父亲节点开始(这里的i代表长度)swap(nums[0],nums[i-1]);//每一次交换树根和(除去数组末尾已经换过的)末尾// print(nums,len);}}int main()
{int len = sizeof(nums)/sizeof(nums[0]);init_rand(nums,len);heap_sort(nums,len);print(nums,len);
}

后序补上解析

相关文章:

考研要求掌握的C语言程度(堆排序)1

含义 堆排序就是把数组的内容在心中建立为大根堆&#xff0c;然后每次循环把根顶和没交换过的根末进行调换&#xff0c;再次建立大根堆的过程 建树的几个公式 一个数组有n个元素 最后一个父亲节点是n/2-1; 假如父亲节点在数组的下标为a 那么左孩子节点在数组下标为2*a1,…...

chronyd配置了local的NTP server之后, NTP报文中出现public IP的问题

描述 客户在Rocky Linux 9.4的VM上配了一个local的NTP server(IP: 10.64.1.76)。 配置完成后, 时钟可以同步&#xff0c;但一段时间后客户的firewall收到告警, 拒绝了大量目标端口为123的请求, 且这些请求的目的IP并不是客户指定的NTP server的IP&#xff0c;客户要求解释原因…...

docker常用命令整理

文章目录 docker 常用操作命令一、镜像类操作1.构建镜像2.从容器创建镜像3.查看镜像列表4.删除镜像5. 从远程镜像仓库拉取镜像6. 将镜像推送到镜像仓库中7. 将镜像导出8. 导入镜像9. 登录镜像仓库 二、容器相关操作1. 运行容器2. 进入容器3. 查看容器的运行状态4. 查看容器的日…...

将CSDN博客转换为PDF的Python Web应用开发--Flask实战

文章目录 项目概述技术栈介绍 项目目录应用结构 功能实现单页博客转换示例&#xff1a; 专栏合集博客转换示例&#xff1a; PDF效果&#xff1a; 代码依赖文件requirements.txt:app.py&#xff1a;代码解释&#xff1a; /api/onepage.py:代码解释&#xff1a; /api/zhuanlan.py…...

AIGC学习笔记(3)——AI大模型开发工程师

文章目录 AI大模型开发工程师002 GPT大模型开发基础1 OpenAI账户注册2 OpenAI官网介绍3 OpenAI GPT费用计算4 OpenAI Key获取与配置5 OpenAI 大模型总览6 代码演示安装依赖导入依赖初始化客户端执行代码遇到的问题 AI大模型开发工程师 002 GPT大模型开发基础 1 OpenAI账户注册…...

Windows server 2003服务器的安装

Windows server 2003服务器的安装 安装前的准备&#xff1a; 1.镜像SN序列号 图1-1 Windows server 2003的安装包非常人性化 2.指定一个安装位置 图1-2 选择好安装位置 3.启动虚拟机打开安装向导 图1-3 打开VMware17安装向导 图1-4 给虚拟光驱插入光盘镜像 图1-5 输入SN并…...

HTML作业

作业 复现下面的图片 复现结果 代码 <!DOCTYPE html> <html><head><meta charset"utf-8"><title></title></head><body><form action"#"method"get"enctype"text/plain"><…...

MYSQL-SQL-04-DCL(Data Control Language,数据控制语言)

DCL&#xff08;数据控制语言&#xff09; DCL英文全称是Data Control Language(数据控制语言)&#xff0c;用来管理数据库用户、控制数据库的访问权限。 一、管理用户 1、查询用户 在MySQL数据库管理系统中&#xff0c;mysql 是一个特殊的系统数据库名称&#xff0c;它并不…...

多线程进阶——线程池的实现

什么是池化技术 池化技术是一种资源管理策略&#xff0c;它通过重复利用已存在的资源来减少资源的消耗&#xff0c;从而提高系统的性能和效率。在计算机编程中&#xff0c;池化技术通常用于管理线程、连接、数据库连接等资源。 我们会将可能使用的资源预先创建好&#xff0c;…...

C++网络编程之C/S模型

C网络编程之C/S模型 引言 在网络编程中&#xff0c;C/S&#xff08;Client/Server&#xff0c;客户端/服务器&#xff09;模型是一种最基本且广泛应用的架构模式。这种模型将应用程序分为两个部分&#xff1a;服务器&#xff08;Server&#xff09;和客户端&#xff08;Clien…...

目标检测:YOLOv11(Ultralytics)环境配置,适合0基础纯小白,超详细

目录 1.前言 2. 查看电脑状况 3. 安装所需软件 3.1 Anaconda3安装 3.2 Pycharm安装 4. 安装环境 4.1 安装cuda及cudnn 4.1.1 下载及安装cuda 4.1.2 cudnn安装 4.2 创建虚拟环境 4.3 安装GPU版本 4.3.1 安装pytorch&#xff08;GPU版&#xff09; 4.3.2 安装ultral…...

面试域——岗位职责以及工作流程

摘要 介绍互联网岗位的职责以及开发流程。在岗位职责方面&#xff0c;详细阐述了产品经理、前端开发工程师、后端开发工程师、测试工程师、运维工程师等的具体工作内容。产品经理负责需求收集、产品规划等&#xff1b;前端专注界面开发与交互&#xff1b;后端涉及系统架构与业…...

C#文件内容检索的功能

为了构建一个高效的文件内容检索系统&#xff0c;我们需要考虑更多的细节和实现策略。以下是对之前技术方案的扩展&#xff0c;以及一个更详细的C# demo示例&#xff0c;其中包含索引构建、多线程处理和文件监控的简化实现思路。 扩展后的技术方案 索引构建&#xff1a; 使用L…...

Redis-05 Redis发布订阅

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;是一种消息通信模式&#xff0c;允许客户端订阅消息频道&#xff0c;以便在发布者向频道发送消息时接收消息。这种模式非常适合实现消息队列、聊天应用、实时通知等功能。 #了解即可&#xff0c;用的很少...

【读书笔记·VLSI电路设计方法解密】问题27:什么是可制造性设计

尽管业界尚未达成共识,但“可制造性设计”这一术语大致描述了旨在提高产品良率的特定分析、预防、纠正和验证工作。这不同于后GDSII阶段的分辨率增强技术,如光学邻近效应校正(OPC)和相位移掩膜(PSM)。“可制造性设计”中的关键词是“设计”,意指在设计阶段(而非设计完成…...

数据结构:堆的应用

堆排序 假定有一组数据极多的数&#xff0c;让我们进行排序&#xff0c;那我们很容易想到一种经典的排序方法&#xff0c;冒泡排序&#xff0c;我们对冒泡排序的时间复杂度进行分析&#xff1a; 显然&#xff0c;冒泡排序的时间复杂度是O&#xff08;n^2&#xff09;,当数据量…...

Spring Boot 实现文件分片上传和下载

文章目录 一、原理分析1.1 文件分片1.2 断点续传和断点下载1.2 文件分片下载的 HTTP 参数 二、文件上传功能实现2.1 客户端(前端)2.2 服务端 三、文件下载功能实现3.1 客户端(前端)3.2 服务端 四、功能测试4.1 文件上传功能测试4.2 文件下载功能实现 参考资料 完整案例代码&…...

夹逼准则求数列极限(复习总结)

记住这两个准则&#xff0c;然后我们就开始看题目 因为是证明题&#xff0c;所以要放缩到什么值已经是确定的了。也就是放缩到0&#xff0c;然后很明显地可以看出前面已经有一个可以使得极限是0了&#xff0c;并且后面的值明显小于1&#xff0c;就是逐渐缩小的趋势&#xff0c;…...

【python】OpenCV—WaterShed Algorithm(1)

文章目录 1、功能描述2、代码实现3、完整代码4、效果展示5、涉及到的库函数5.1、cv2.pyrMeanShiftFiltering5.2、cv2.morphologyEx5.3、cv2.distanceTransform5.4、cv2.normalize5.5、cv2.watershed 6、参考 1、功能描述 基于分水岭算法对图片进行分割 分水岭分割算法&#x…...

查找与排序-插入排序

思考&#xff1a;在把待排序的元素插入已经有序的子序列中时&#xff0c;是不是一定要逐一比较&#xff1f;有没有改进方法&#xff1f; 在查找插入位置的时候可以采用折半&#xff08;二分&#xff09;搜索的办法。 一、折半插入排序 1.折半插入排序算法的基本思想 假设待…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...