当前位置: 首页 > 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.折半插入排序算法的基本思想 假设待…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

五、jmeter脚本参数化

目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...

Qt Quick Controls模块功能及架构

Qt Quick Controls是Qt Quick的一个附加模块&#xff0c;提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中&#xff0c;这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构&#xff0c;与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...

智能体革命:企业如何构建自主决策的AI代理?

OpenAI智能代理构建实用指南详解 随着大型语言模型&#xff08;LLM&#xff09;在推理、多模态理解和工具调用能力上的进步&#xff0c;智能代理&#xff08;Agents&#xff09;成为自动化领域的新突破。与传统软件仅帮助用户自动化流程不同&#xff0c;智能代理能够自主执行工…...