当前位置: 首页 > 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;并通过括号里面的东西搜索当前…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...