C语言实现排序之堆排序算法
一、堆排序算法
基本思想
堆排序是一种比较有效的排序方法,其基本思想是:
- 构建最大堆:首先将待排序的数组构建成一个最大堆,即对于每个非叶子节点,它的值都大于或等于其子节点的值。
- 排序:然后将堆顶元素(最大值)与堆的最后一个元素交换位置,将其移出堆,并调整剩余元素以保持最大堆的性质。
步骤
- 构建最大堆:从最后一个非叶子节点开始,逐个调整子树,使之满足最大堆的条件。
- 排序:重复以下操作直到堆为空:
- 将堆顶元素(最大值)与堆的最后一个元素交换位置。
- 重新调整剩余元素以保持最大堆的性质。
示例
假设我们有一个数组 [5, 2, 4, 6, 1, 3]
:
- 构建最大堆:
[5, 2, 4, 6, 1, 3]
->[6, 5, 4, 2, 1, 3]
- 排序:
- 将最大的元素
6
移动到数组的末尾,然后重新调整剩余元素以保持最大堆的性质。 - 重复此过程,直到所有元素都被排序。
- 将最大的元素
性能分析
- 时间复杂度:O(n log n),其中 n 是数组中的元素数量。
- 空间复杂度:O(1)(原地排序)。
二、代码
#include <stdlib.h>
#include <stdio.h>
#include <time.h>// 函数声明
int* create_and_generate_random_array(int size);
void print_array(int *array, int size);
void heapify(int *array, int n, int i);
void heap_sort(int *array, int size);
int generate_random_size();int main() {int size = generate_random_size(); // 随机生成数组大小int *array = create_and_generate_random_array(size);if (array == NULL) {// 如果内存分配失败printf("Memory allocation failed\n");free(array);return 1;}// 打印原始数组(如果需要,可以取消注释)// printf("Original array:\n");// print_array(array, size);// 获取开始时间clock_t start_time = clock();// 对数组进行堆排序heap_sort(array, size);// 获取结束时间clock_t end_time = clock();// 计算时间差并转换为毫秒double execution_time = ((double)(end_time - start_time) / CLOCKS_PER_SEC) * 1000;// 打印排序后的数组(如果需要,可以取消注释)// printf("Sorted array:\n");// print_array(array, size);printf("array_size = %d\n", size);// 打印执行时间printf("Execution time: %.2f ms\n", execution_time);// 释放分配的内存free(array);return 0;
}// 生成随机数组大小
int generate_random_size() {srand(time(NULL));return rand() % 9000 + 1000; // 生成1000到9999之间的随机数
}// 创建并生成随机数组
int* create_and_generate_random_array(int size) {int *array = (int *)malloc(sizeof(int) * size);if (array == NULL) {// 如果内存分配失败return NULL;}// 使用当前时间作为随机数种子srand(time(NULL));for (int i = 0; i < size; i++) {array[i] = rand() % 1000; // 生成0到999之间的随机数}return array;
}// 打印数组
void print_array(int *array, int size) {for (int i = 0; i < size; i++) {printf("%d ", array[i]);}printf("\n");
}// 构建最大堆
void heapify(int *array, int n, int i) {int largest = i; // 初始化最大值索引int left = 2 * i + 1; // 左子节点int right = 2 * i + 2; // 右子节点// 如果左子节点大于根if (left < n && array[left] > array[largest])largest = left;// 如果右子节点大于当前最大值if (right < n && array[right] > array[largest])largest = right;// 如果最大值不是根if (largest != i) {int swap = array[i];array[i] = array[largest];array[largest] = swap;// 递归地堆化受影响的子树heapify(array, n, largest);}
}// 堆排序
void heap_sort(int *array, int size) {// 构建最大堆for (int i = size / 2 - 1; i >= 0; i--)heapify(array, size, i);// 一个接一个从堆顶取出元素for (int i = size - 1; i > 0; i--) {// 将当前根(最大值)移动到数组末尾int temp = array[0];array[0] = array[i];array[i] = temp;// 调整剩余堆,使其成为最大堆heapify(array, i, 0);}
}
相关文章:
C语言实现排序之堆排序算法
一、堆排序算法 基本思想 堆排序是一种比较有效的排序方法,其基本思想是: 构建最大堆:首先将待排序的数组构建成一个最大堆,即对于每个非叶子节点,它的值都大于或等于其子节点的值。排序:然后将堆顶元素…...

【STM32 Blue Pill编程】-外部中断配置及使用
外部中断配置及使用 文章目录 外部中断配置及使用1、中断介绍2、STM32中的中断3、硬件准备及接线4、GPIO配置5、代码实现在本文中,我们将介绍如何使用 STM32Cube IDE 中的 HAL 库配置和处理外部中断。 我们将通过一个带有按钮和 LED 的示例来演示这一点。 读完本文后,您将能够…...
MySQL 安装与配置教程:单机、主从复制与集群模式
目录 MySQL 简介MySQL 安装MySQL 基础配置MySQL 主从复制配置MySQL 集群配置总结 1. MySQL 简介 MySQL 是一个广泛使用的关系型数据库管理系统,具有高性能、高可靠性和易用性等特点。它支持多种部署模式,包括单机模式、主从复制模式(用于高…...

JavaEE 的相关知识点(一)
一、过滤器 过滤器(Filter)是一个用于对请求和响应进行预处理的组件。过滤器可以在 Java Servlet 规范中使用,通常用于执行一些通用的任务 1、过滤器的作用 过滤器是一种javaEE规范中定义的一种技术,可以让请求达到目标servlet之…...
使用Python实现深度学习模型:智能医疗影像识别与诊断
介绍 智能医疗影像识别与诊断是现代医疗技术的重要应用,通过深度学习模型,可以自动分析和识别医疗影像,提高诊断的准确性和效率。本文将介绍如何使用Python和深度学习技术来实现智能医疗影像识别与诊断。 环境准备 首先,我们需要安装一些必要的Python库: pip install …...
24.给定一个链表,实现一个算法交换每两个相邻节点并返回其头部。要求不能修改列表节点中的值,只能更改节点本身。
24. Swap Nodes in Pairs 题目 给定一个链表,交换每两个相邻节点并返回其头部。要求不能修改列表节点中的值,只能更改节点本身。 Example: Given 1->2->3->4, you should return the list as 2->1->4->3....
Python 通过UDP传输超过64k的信息
Python 通过UDP传输超过64k的信息 在网络编程中,UDP(用户数据报协议)是一种常用的传输协议。与TCP不同,UDP是无连接的,并且不保证数据包的顺序、完整性及交付。尽管如此,UDP因其较低的延迟和开销而被广泛应…...
微服务设计原则——高性能:批量
能批量就不要并发。 如果调用方需要调用我们接口多次才能进行一个完整的操作,那么这个接口设计就可能有问题。 比如获取数据的接口,如果仅仅提供getData(int id)接口,那么使用方如果要一次性获取 20 个数据,它就需要循环遍历调用…...

C:指针学习-指针变量—学习笔记
今日伊雷娜: 目录 前言: 1、字符指针变量 1.1 使用字符指针存放字符 1.2 使用字符指针变量存放字符串 2、数组指针变量 2.1 什么是数组指针变量? 2.2 数组指针变量初始化 2.3 关于数组指针类型的解析 3、函数指针变量 3.1 函数地址 …...

【MySQL 07】表的增删查改 (带思维导图)
文章目录 🌈 一、insert 添加数据⭐ 1. 单行数据 全列插入⭐ 2. 多行数据 指定列插入⭐ 3. 插入否则更新⭐4. 插入否则替换 🌈 二、select 查询数据⭐ 1. select 列🌙 1.1 全列查询🌙 1.2 指定列查询🌙 1.3 查询字段…...

快速上手Git
Git相关概念 Git是一个开源的分布式版本控制系统,由Linus Torvalds在2005年创建,用于有效、高速地处理从小到大的项目版本管理。它是由 Linux 之父 Linus Torvalds 开发的,并已经成为了现代软件开发领域中最流行的版本控制系统之一。 git的工…...

RTC时钟测试
1. 基础知识 Linux 的系统时间有时跟硬件时间是不同步的。 Linux时钟分为系统时钟(System Clock)和硬件(Real Time Clock,简称RTC)时钟。系统时钟是指当前Linux Kernel中的时钟,而硬件时钟则是主板上由电池供电的时钟,这个硬件时钟可以在BIO…...

大数据技术——实战项目:广告数仓(第六部分)报表数据导出至clickhouse
目录 第11章 报表数据导出 11.1 Clickhouse安装 11.2 Clickhouse建表 11.2.1 创建database 11.2.2 创建table 11.3 Hive数据导出至Clickhouse 第11章 报表数据导出 由于本项目最终要出的报表,要求具备交互功能,以及进行自助分析的能力,…...

Android studio模拟制作-简易的订餐交易小案例
一、最终呈现效果 订餐支付小案例效果 二、布局设计activity_main.xml <?xml version"1.0" encoding"utf-8"?> <androidx.constraintlayout.widget.ConstraintLayout xmlns:android"http://schemas.android.com/apk/res/android"xml…...

消防隐患在线小程序的设计
管理员账户功能包括:系统首页,个人中心,用户管理,消防隐患举报管理,消防隐患分类管理,统计分类管理,处理结果管理,系统管理 微信端账号功能包括:系统首页,我…...

【Vue3】路由Params传参
【Vue3】路由Params传参 背景简介开发环境开发步骤及源码总结 背景 随着年龄的增长,很多曾经烂熟于心的技术原理已被岁月摩擦得愈发模糊起来,技术出身的人总是很难放下一些执念,遂将这些知识整理成文,以纪念曾经努力学习奋斗的日…...

授权cleanmymac访问全部磁盘 Mac授权访问权限 cleanmymac缺少权限
CleanMyMac是Mac系统下的一款专业的苹果电脑清理软件,同时也是一款优秀的电脑系统管理软件。它能有效清理系统垃圾,快速释放磁盘内存,缓解卡顿现象,保障系统顺畅地运行。 全磁盘访问权限,就好比机场内进行的安全检查。…...
Ubuntu/18.04 LTS下编译 BoringSSL 库
1、准备一个 Ubuntu/18.04 LTS 系统的设备 2、安装软件 GIT、GCC、CMAKE、G、Golang:1.16 及以上版本 3、克隆仓库源 git clone https://boringssl.googlesource.com/boringssl cd boringssl 4、使用特定版本 git checkout 9fc1c33e9c21439ce5f87855a6591a9324e569fd 5、编…...

【stm32项目】多功能智能家居室内灯光控制系统设计与实现(完整工程资料源码)
多功能智能家居室内灯光控制系统设计与实现 目录: 目录: 前言: 一、项目背景与目标 二、国内外研究现状: 2.1 国内研究现状: 2.2 国外研究现状: 2.3 发展趋势 三、硬件电路设计 3.1 总体概述 3.2 硬件连接总…...

xss靶场详解
目录 1.第一题 2.第二题 3.第三题 4.第四题 5.第五题 6.第六题 7.第七题 8.第八题 1.第一题 在源码script标签里边,innerhtml是用于访问或修改 HTML 元素内的 HTML 内容的,这里是访问spaghet这个元素的,并通过括号里面的东西搜索当前…...

Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...

Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...

DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...