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

C语言实现排序之堆排序算法

一、堆排序算法

基本思想

堆排序是一种比较有效的排序方法,其基本思想是:

  1. 构建最大堆:首先将待排序的数组构建成一个最大堆,即对于每个非叶子节点,它的值都大于或等于其子节点的值。
  2. 排序:然后将堆顶元素(最大值)与堆的最后一个元素交换位置,将其移出堆,并调整剩余元素以保持最大堆的性质。
步骤
  1. 构建最大堆:从最后一个非叶子节点开始,逐个调整子树,使之满足最大堆的条件。
  2. 排序:重复以下操作直到堆为空:
    • 将堆顶元素(最大值)与堆的最后一个元素交换位置。
    • 重新调整剩余元素以保持最大堆的性质。
示例

假设我们有一个数组 [5, 2, 4, 6, 1, 3]

  1. 构建最大堆
    • [5, 2, 4, 6, 1, 3] -> [6, 5, 4, 2, 1, 3]
  2. 排序
    • 将最大的元素 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语言实现排序之堆排序算法

一、堆排序算法 基本思想 堆排序是一种比较有效的排序方法&#xff0c;其基本思想是&#xff1a; 构建最大堆&#xff1a;首先将待排序的数组构建成一个最大堆&#xff0c;即对于每个非叶子节点&#xff0c;它的值都大于或等于其子节点的值。排序&#xff1a;然后将堆顶元素…...

【STM32 Blue Pill编程】-外部中断配置及使用

外部中断配置及使用 文章目录 外部中断配置及使用1、中断介绍2、STM32中的中断3、硬件准备及接线4、GPIO配置5、代码实现在本文中,我们将介绍如何使用 STM32Cube IDE 中的 HAL 库配置和处理外部中断。 我们将通过一个带有按钮和 LED 的示例来演示这一点。 读完本文后,您将能够…...

MySQL 安装与配置教程:单机、主从复制与集群模式

目录 MySQL 简介MySQL 安装MySQL 基础配置MySQL 主从复制配置MySQL 集群配置总结 1. MySQL 简介 MySQL 是一个广泛使用的关系型数据库管理系统&#xff0c;具有高性能、高可靠性和易用性等特点。它支持多种部署模式&#xff0c;包括单机模式、主从复制模式&#xff08;用于高…...

JavaEE 的相关知识点(一)

一、过滤器 过滤器&#xff08;Filter&#xff09;是一个用于对请求和响应进行预处理的组件。过滤器可以在 Java Servlet 规范中使用&#xff0c;通常用于执行一些通用的任务 1、过滤器的作用 过滤器是一种javaEE规范中定义的一种技术&#xff0c;可以让请求达到目标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的信息 在网络编程中&#xff0c;UDP&#xff08;用户数据报协议&#xff09;是一种常用的传输协议。与TCP不同&#xff0c;UDP是无连接的&#xff0c;并且不保证数据包的顺序、完整性及交付。尽管如此&#xff0c;UDP因其较低的延迟和开销而被广泛应…...

微服务设计原则——高性能:批量

能批量就不要并发。 如果调用方需要调用我们接口多次才能进行一个完整的操作&#xff0c;那么这个接口设计就可能有问题。 比如获取数据的接口&#xff0c;如果仅仅提供getData(int id)接口&#xff0c;那么使用方如果要一次性获取 20 个数据&#xff0c;它就需要循环遍历调用…...

C:指针学习-指针变量—学习笔记

今日伊雷娜&#xff1a; 目录 前言&#xff1a; 1、字符指针变量 1.1 使用字符指针存放字符 1.2 使用字符指针变量存放字符串 2、数组指针变量 2.1 什么是数组指针变量&#xff1f; 2.2 数组指针变量初始化 2.3 关于数组指针类型的解析 3、函数指针变量 3.1 函数地址 …...

【MySQL 07】表的增删查改 (带思维导图)

文章目录 &#x1f308; 一、insert 添加数据⭐ 1. 单行数据 全列插入⭐ 2. 多行数据 指定列插入⭐ 3. 插入否则更新⭐4. 插入否则替换 &#x1f308; 二、select 查询数据⭐ 1. select 列&#x1f319; 1.1 全列查询&#x1f319; 1.2 指定列查询&#x1f319; 1.3 查询字段…...

快速上手Git

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

RTC时钟测试

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

大数据技术——实战项目:广告数仓(第六部分)报表数据导出至clickhouse

目录 第11章 报表数据导出 11.1 Clickhouse安装 11.2 Clickhouse建表 11.2.1 创建database 11.2.2 创建table 11.3 Hive数据导出至Clickhouse 第11章 报表数据导出 由于本项目最终要出的报表&#xff0c;要求具备交互功能&#xff0c;以及进行自助分析的能力&#xff0c;…...

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…...

消防隐患在线小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;消防隐患举报管理&#xff0c;消防隐患分类管理&#xff0c;统计分类管理&#xff0c;处理结果管理&#xff0c;系统管理 微信端账号功能包括&#xff1a;系统首页&#xff0c;我…...

【Vue3】路由Params传参

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

授权cleanmymac访问全部磁盘 Mac授权访问权限 cleanmymac缺少权限

CleanMyMac是Mac系统下的一款专业的苹果电脑清理软件&#xff0c;同时也是一款优秀的电脑系统管理软件。它能有效清理系统垃圾&#xff0c;快速释放磁盘内存&#xff0c;缓解卡顿现象&#xff0c;保障系统顺畅地运行。 全磁盘访问权限&#xff0c;就好比机场内进行的安全检查。…...

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项目】多功能智能家居室内灯光控制系统设计与实现(完整工程资料源码)

多功能智能家居室内灯光控制系统设计与实现 目录&#xff1a; 目录&#xff1a; 前言&#xff1a; 一、项目背景与目标 二、国内外研究现状&#xff1a; 2.1 国内研究现状&#xff1a; 2.2 国外研究现状&#xff1a; 2.3 发展趋势 三、硬件电路设计 3.1 总体概述 3.2 硬件连接总…...

xss靶场详解

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

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启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 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

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是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

DingDing机器人群消息推送

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