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这个元素的,并通过括号里面的东西搜索当前…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
