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

【排序 - 选择排序优化版(利用堆排序)】

结合选择排序和堆排序的思路,可以通过利用堆数据结构来优化选择排序的过程,使得排序算法更加高效。在这种结合中,我们利用堆的特性来快速定位和选择未排序部分的最小元素,避免了选择排序中每次线性搜索的开销。

选择排序和堆排序结合的思路

选择排序的基本思想是每次从未排序的部分选择最小(或最大)的元素,放到已排序部分的末尾。结合堆排序的思路,我们可以利用最小堆来维护未排序部分的元素,每次从堆顶取出最小元素,放入已排序部分,然后调整堆,以保持堆的性质。

实现步骤

  1. 建立最小堆:将待排序的数组建立成一个最小堆。
  2. 选择最小元素:从堆顶(最小值)开始选择,将其放入已排序部分。
  3. 维护堆的性质:每次选择操作后,需要调整堆,使得剩余的元素依然构成最小堆。
  4. 重复以上步骤:直到所有元素都被排序。

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() 函数对数组进行排序,并输出排序后的结果。

这种结合选择排序和堆排序的方法利用了堆的优势,使得选择过程更高效,从而提升了整体排序算法的性能。

相关文章:

【排序 - 选择排序优化版(利用堆排序)】

结合选择排序和堆排序的思路&#xff0c;可以通过利用堆数据结构来优化选择排序的过程&#xff0c;使得排序算法更加高效。在这种结合中&#xff0c;我们利用堆的特性来快速定位和选择未排序部分的最小元素&#xff0c;避免了选择排序中每次线性搜索的开销。 选择排序和堆排序…...

PHP编程开发工具有哪些?

PHP的开发工具种类繁多&#xff0c;涵盖了从集成开发环境&#xff08;IDE&#xff09;、代码编辑器、调试器到版本控制工具和数据库管理工具等多个方面。以下是一些常见的PHP开发工具&#xff1a; 1. 集成开发环境&#xff08;IDE&#xff09; PhpStorm&#xff1a;由JetBrai…...

火柴棒图python绘画

使用Python绘制二项分布的概率质量函数&#xff08;PMF&#xff09; 在这篇博客中&#xff0c;我们将探讨如何使用Python中的scipy库和matplotlib库来绘制二项分布的概率质量函数&#xff08;PMF&#xff09;。二项分布是统计学中常见的离散概率分布&#xff0c;描述了在固定次…...

Nginx七层(应用层)反向代理:UWSGI代理uwsgi_pass篇

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

Effective C++笔记之二十一:One Definition Rule(ODR)

ODR细节有点复杂&#xff0c;跨越各种情况。基本内容如下&#xff1a; ●普通&#xff08;非模板&#xff09;的noninline函数和成员函数、noninline全局变量、静态数据成员在整个程序中都应当只定义一次。 ●class类型&#xff08;包括structs和unions&#xff09;、模板&…...

探索未来:Transformer模型在智能环境监测的革命性应用

探索未来&#xff1a;Transformer模型在智能环境监测的革命性应用 在当今数字化时代&#xff0c;环境监测正逐渐从传统的人工检测方式转变为智能化、自动化的系统。Transformer模型&#xff0c;作为深度学习领域的一颗新星&#xff0c;其在自然语言处理&#xff08;NLP&#x…...

Nginx中文URL请求404

这两天正在搞我的静态网站。方案是&#xff1a;从思源笔记Markdown笔记&#xff0c;用MkOcs build成静态网站&#xff0c;上传到到Nginx服务器。遇到一个问题&#xff1a;URL含有中文会404&#xff0c;全英文URL则正常访问。 ‍ 比如&#xff1a; ​​ ‍ 设置了utf-8 ht…...

33. 动量法(Momentum)介绍

1. 背景知识 在深度学习的优化过程中&#xff0c;梯度下降法&#xff08;Gradient Descent, GD&#xff09;是最基本的方法。然而&#xff0c;基本的梯度下降法在实际应用中存在收敛速度慢、容易陷入局部最小值以及在高维空间中振荡较大的问题。为了解决这些问题&#xff0c;人…...

Python | Leetcode Python题解之第228题汇总区间

题目&#xff1a; 题解&#xff1a; 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/蜂窝无线电认证&#xff0c;对跨地区应用场景&#xff0c;特别重要。跟随全球业务的脚步&#xff0c;我们像大唐先辈一样走遍全球业务的时候&#xff0c;了解一点全球化的 知识信息&#xff0c;就显得有那么点意义。 NA &#xff08;北美&#xff09;&#xff1a;美国和加…...

如何指定多块GPU卡进行训练-数据并行

训练代码&#xff1a; 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 驱动测试

若该文为原创文章&#xff0c;转载请注明原文出处。 报着学习态度&#xff0c;接下来学习驱动是如何使用的&#xff0c;从简单的helloworld驱动学习起。 开始编写第一个驱动程序—helloworld 驱动。 一、环境 1、开发板&#xff1a;正点原子的ATK-DLRK3568 2、系统&#xf…...

【智能制造-14】机器视觉软件

CCD相机和COMS相机? CCD&#xff08;Charge-Coupled Device&#xff09;相机和CMOS&#xff08;Complementary Metal-Oxide-Semiconductor&#xff09;相机是两种常见的数字图像传感器技术&#xff0c;用于捕捉和处理图像。 CCD相机&#xff1a; CCD相机使用一种称为CCD的光电…...

MVC分页

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

webGL可用的14种3D文件格式,但要具体问题具体分析。

hello&#xff0c;我威斯数据&#xff0c;你在网上看到的各种炫酷的3d交互效果&#xff0c;背后都必须有三维文件支撑&#xff0c;就好比你网页的时候&#xff0c;得有设计稿源文件一样。WebGL是一种基于OpenGL ES 2.0标准的3D图形库&#xff0c;可以在网页上实现硬件加速的3D图…...

HybridCLR原理中的重点总结

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

昇思学习打卡-14-ResNet50迁移学习

文章目录 数据集可视化预训练模型的使用部分实现 推理 迁移学习&#xff1a;在一个很大的数据集上训练得到一个预训练模型&#xff0c;然后使用该模型来初始化网络的权重参数或作为固定特征提取器应用于特定的任务中。本章学习使用的是前面学过的ResNet50&#xff0c;使用迁移学…...

软件开发面试题C#,.NET知识点(续)

1.C#中的封装是什么&#xff0c;以及它的重要性。 封装&#xff08;Encapsulation&#xff09; 是面向对象编程&#xff08;OOP&#xff09;的一个基本概念。它指的是将对象的状态&#xff08;属性&#xff09;和行为&#xff08;方法&#xff09;绑定在一起&#xff0c;并且将…...

2019年美赛题目Problem A: Game of Ecology

本题分析&#xff1a; 本题想要要求从实际生物角度出发&#xff0c;对权力游戏中龙这种虚拟生物的生态环境和生物特性进行建模&#xff0c;感觉属于比较开放类型的题目&#xff0c;重点在于参考生物的选择&#xff0c;龙虽然是虚拟的但是龙的生态特性可以参考目前生物圈里存在…...

沙龙回顾|MongoDB如何充当企业开发加速器?

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

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

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

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...