【排序 - 选择排序优化版(利用堆排序)】
结合选择排序和堆排序的思路,可以通过利用堆数据结构来优化选择排序的过程,使得排序算法更加高效。在这种结合中,我们利用堆的特性来快速定位和选择未排序部分的最小元素,避免了选择排序中每次线性搜索的开销。
选择排序和堆排序结合的思路
选择排序的基本思想是每次从未排序的部分选择最小(或最大)的元素,放到已排序部分的末尾。结合堆排序的思路,我们可以利用最小堆来维护未排序部分的元素,每次从堆顶取出最小元素,放入已排序部分,然后调整堆,以保持堆的性质。
实现步骤
- 建立最小堆:将待排序的数组建立成一个最小堆。
- 选择最小元素:从堆顶(最小值)开始选择,将其放入已排序部分。
- 维护堆的性质:每次选择操作后,需要调整堆,使得剩余的元素依然构成最小堆。
- 重复以上步骤:直到所有元素都被排序。
C语言代码实现
下面是利用C语言实现结合选择排序和堆排序思路的示例代码:
#include <stdio.h>// 函数:对数组的子树以根节点 i 进行堆化,n 是堆的大小
void heapify(int arr[], int n, int i) {int smallest = i; // 初始化最小值索引为 iint left = 2 * i + 1; // 左子节点索引为 2*i + 1int right = 2 * i + 2; // 右子节点索引为 2*i + 2// 如果左子节点比根节点小if (left < n && arr[left] < arr[smallest])smallest = left;// 如果右子节点比当前最小值小if (right < n && arr[right] < arr[smallest])smallest = right;// 如果最小值不是根节点if (smallest != i) {// 交换最小值和根节点int temp = arr[i];arr[i] = arr[smallest];arr[smallest] = temp;// 递归调整受影响的子树heapify(arr, n, smallest);}
}// 函数:进行堆排序
void heapSort(int arr[], int n) {// 构建堆(重新排列数组)for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);// 依次从堆中提取元素for (int i = n - 1; i > 0; i--) {// 将当前根节点移至末尾int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 对剩余堆进行堆化heapify(arr, i, 0);}
}// 函数:利用堆排序原理执行选择排序
void selectionHeapSort(int arr[], int n) {// 从数组构建最小堆heapSort(arr, n);// 现在 arr[0] 包含最小元素,将其移到末尾并重复for (int i = 0; i < n; i++) {// 交换 arr[0] 和 arr[i]int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 重建堆,排除已排序的最后一个元素heapify(arr, i, 0);}
}// 函数:打印数组
void printArray(int arr[], int n) {for (int i = 0; i < n; ++i)printf("%d ", arr[i]);printf("\n");
}// 主函数:测试以上功能
int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组:\n");printArray(arr, n);selectionHeapSort(arr, n);printf("选择和堆排序结合后的排序数组:\n");printArray(arr, n);return 0;
}
}
示例说明
在上面的代码中:
heapify()
函数用于维护堆的性质。heapSort()
函数用于对数组进行堆排序。selectionHeapSort()
函数结合了选择排序和堆排序的思路,通过建立最小堆和每次选择操作来实现排序。main()
函数中展示了如何使用selectionHeapSort()
函数对数组进行排序,并输出排序后的结果。
这种结合选择排序和堆排序的方法利用了堆的优势,使得选择过程更高效,从而提升了整体排序算法的性能。
相关文章:
【排序 - 选择排序优化版(利用堆排序)】
结合选择排序和堆排序的思路,可以通过利用堆数据结构来优化选择排序的过程,使得排序算法更加高效。在这种结合中,我们利用堆的特性来快速定位和选择未排序部分的最小元素,避免了选择排序中每次线性搜索的开销。 选择排序和堆排序…...
PHP编程开发工具有哪些?
PHP的开发工具种类繁多,涵盖了从集成开发环境(IDE)、代码编辑器、调试器到版本控制工具和数据库管理工具等多个方面。以下是一些常见的PHP开发工具: 1. 集成开发环境(IDE) PhpStorm:由JetBrai…...

火柴棒图python绘画
使用Python绘制二项分布的概率质量函数(PMF) 在这篇博客中,我们将探讨如何使用Python中的scipy库和matplotlib库来绘制二项分布的概率质量函数(PMF)。二项分布是统计学中常见的离散概率分布,描述了在固定次…...

Nginx七层(应用层)反向代理:UWSGI代理uwsgi_pass篇
Nginx七层(应用层)反向代理 UWSGI代理uwsgi_pass篇 - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite:http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this a…...

Effective C++笔记之二十一:One Definition Rule(ODR)
ODR细节有点复杂,跨越各种情况。基本内容如下: ●普通(非模板)的noninline函数和成员函数、noninline全局变量、静态数据成员在整个程序中都应当只定义一次。 ●class类型(包括structs和unions)、模板&…...
探索未来:Transformer模型在智能环境监测的革命性应用
探索未来:Transformer模型在智能环境监测的革命性应用 在当今数字化时代,环境监测正逐渐从传统的人工检测方式转变为智能化、自动化的系统。Transformer模型,作为深度学习领域的一颗新星,其在自然语言处理(NLP&#x…...

Nginx中文URL请求404
这两天正在搞我的静态网站。方案是:从思源笔记Markdown笔记,用MkOcs build成静态网站,上传到到Nginx服务器。遇到一个问题:URL含有中文会404,全英文URL则正常访问。 比如: 设置了utf-8 ht…...
33. 动量法(Momentum)介绍
1. 背景知识 在深度学习的优化过程中,梯度下降法(Gradient Descent, GD)是最基本的方法。然而,基本的梯度下降法在实际应用中存在收敛速度慢、容易陷入局部最小值以及在高维空间中振荡较大的问题。为了解决这些问题,人…...

Python | Leetcode Python题解之第228题汇总区间
题目: 题解: class Solution:def summaryRanges(self, nums: List[int]) -> List[str]:def f(i: int, j: int) -> str:return str(nums[i]) if i j else f{nums[i]}->{nums[j]}i 0n len(nums)ans []while i < n:j iwhile j 1 < n …...
物联网应用,了解一点 WWAN全球网络标准
WWAN/蜂窝无线电认证,对跨地区应用场景,特别重要。跟随全球业务的脚步,我们像大唐先辈一样走遍全球业务的时候,了解一点全球化的 知识信息,就显得有那么点意义。 NA (北美):美国和加…...

如何指定多块GPU卡进行训练-数据并行
训练代码: train.py import torch import torch.nn as nn import torch.optim as optim from torch.utils.data import DataLoader, Dataset import torch.nn.functional as F# 假设我们有一个简单的文本数据集 class TextDataset(Dataset):def __init__(self, te…...

RK3568笔记三十三: helloworld 驱动测试
若该文为原创文章,转载请注明原文出处。 报着学习态度,接下来学习驱动是如何使用的,从简单的helloworld驱动学习起。 开始编写第一个驱动程序—helloworld 驱动。 一、环境 1、开发板:正点原子的ATK-DLRK3568 2、系统…...
【智能制造-14】机器视觉软件
CCD相机和COMS相机? CCD(Charge-Coupled Device)相机和CMOS(Complementary Metal-Oxide-Semiconductor)相机是两种常见的数字图像传感器技术,用于捕捉和处理图像。 CCD相机: CCD相机使用一种称为CCD的光电…...

MVC分页
public ActionResult Index(int ? page){IPagedList<EF.ACCOUNT> userPagedList;using (EF.eMISENT content new EF.eMISENT()){第几页int pageNumber page ?? 1;每页数据条数,这个可以放在配置文件中int pageSize 10;//var infoslist.C660List.OrderBy(…...

webGL可用的14种3D文件格式,但要具体问题具体分析。
hello,我威斯数据,你在网上看到的各种炫酷的3d交互效果,背后都必须有三维文件支撑,就好比你网页的时候,得有设计稿源文件一样。WebGL是一种基于OpenGL ES 2.0标准的3D图形库,可以在网页上实现硬件加速的3D图…...

HybridCLR原理中的重点总结
序言 该文章以一个新手的身份,讲一下自己学习的经过,大家更快的学习HrbirdCLR。 我之前的两个Unity项目中,都使用到了热更新功能,而热更新的技术栈都是用的HybridCLR。 第一个项目本身虽然已经集成好了热更逻辑(使用…...

昇思学习打卡-14-ResNet50迁移学习
文章目录 数据集可视化预训练模型的使用部分实现 推理 迁移学习:在一个很大的数据集上训练得到一个预训练模型,然后使用该模型来初始化网络的权重参数或作为固定特征提取器应用于特定的任务中。本章学习使用的是前面学过的ResNet50,使用迁移学…...
软件开发面试题C#,.NET知识点(续)
1.C#中的封装是什么,以及它的重要性。 封装(Encapsulation) 是面向对象编程(OOP)的一个基本概念。它指的是将对象的状态(属性)和行为(方法)绑定在一起,并且将…...
2019年美赛题目Problem A: Game of Ecology
本题分析: 本题想要要求从实际生物角度出发,对权力游戏中龙这种虚拟生物的生态环境和生物特性进行建模,感觉属于比较开放类型的题目,重点在于参考生物的选择,龙虽然是虚拟的但是龙的生态特性可以参考目前生物圈里存在…...

沙龙回顾|MongoDB如何充当企业开发加速器?
数据不仅是企业发展转型的驱动力,也是开发者最棘手的问题。前日,MongoDB携手阿里云、NineData在杭州成功举办了“数据驱动,敏捷前行——MongoDB企业开发加速器”技术沙龙。此次活动吸引了来自各行各业的专业人员,共同探讨MongoDB的…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...

PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...