当前位置: 首页 > 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的…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...