【八大排序】选择排序 | 堆排序 + 图文详解!!

在这里插入图片描述

📷 江池俊: 个人主页
🔥个人专栏: ✅数据结构冒险记 ✅C语言进阶之路
🌅 有航道的人,再渺小也不会迷途。


在这里插入图片描述

文章目录

    • 一、选择排序
      • 1.1 基本思想
      • 1.2 算法步骤 + 动图演示
      • 1.3 代码实现
      • 1.4 选择排序特性总结
    • 二、堆排序
      • 2.1 堆排序概念
      • 2.2 算法步骤 + 动图演示
      • 2.3 代码实现
      • 2.4 堆排序特性总结

在这里插入图片描述

一、选择排序

1.1 基本思想

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。

1.2 算法步骤 + 动图演示

  1. 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
  2. 若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换
  3. 在剩余的array[i]--array[n-2]array[i+1]--array[n-1])集合中,重复上述步骤,直到集合剩余 1 个元素

在这里插入图片描述

1.3 代码实现

这里我们的代码可以稍作优化,在每次选数的时候一次性选出最大和最小的
数,然后依次与数组最后一个和第一个数进行交换。

void Swap(int* p1, int* p2)
{int temp = *p1;*p1 = *p2;*p2 = temp;
}// 选择排序
// 时间复杂度:O(N^2)
// 最好的情况下:O(N^2)
void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = 1; i <= end; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);if (maxi == begin){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

1.4 选择排序特性总结

  1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

二、堆排序

堆排序传送门:二叉树堆的应用实例分析:堆排序 | TOP-K问题

虽然上面已经讲解过堆排序,但在此我们最好还是继续回顾一下堆排序的算法思想。

2.1 堆排序概念

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:

  1. 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列
  2. 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列

2.2 算法步骤 + 动图演示

  1. 创建一个堆 H[0……n-1];(建议使用向下调整建堆)
  2. 把堆首(最大值)和堆尾互换;
  3. 把堆的尺寸缩小 1(即确定最后一个数的位置),并调用 向下调整算法,目的是把新的数组顶端数据调整到相应位置;
  4. 重复步骤 2,直到堆的尺寸为 1。

在这里插入图片描述

2.3 代码实现

以下代码以升序排序为例,降序排序类似。
注意:建堆时,使用向下调整法要从倒数第一个非叶子节点(即最后一个叶子节点的父节点)开始。

// 向下调整
void AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){// 假设左孩子小,如果假设错了,更新一下if (child + 1 < size && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 堆排序 --- 升序
void HeapSort(int* a, int n)
{// O(N)// 建大堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n,i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

2.4 堆排序特性总结

  1. 堆排序使用堆来选数,效率就高了很多。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/252067.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Vue3项目封装一个Element-plus Pagination分页

前言:后台系统分页肯定是离不开的,但是ui框架都很多,我们可以定义封装一种格式,所有项目按到这个结构来做. 实例: 第一步:在项目components组件新建一个分页组件,用来进行封装组件. 第二步:根据官方的进行定义,官方提供的这些,需要我们封装成动态模式 第三步:代码改造 <!-…

aspose-words基础功能演示

我们在Aspose.Words中使用术语“渲染”来描述将文档转换为文件格式或分页或具有页面概念的介质的过程。我们正在讨论将文档呈现为页面。下图显示了 Aspose.Words 中的渲染情况。 Aspose.Words 的渲染功能使您能够执行以下操作: 将文档或选定页面转换为 PDF、XPS、HTML、XAML、…

MySQL操作问题汇总

MySQL操作问题汇总 1.无法远程连接Ubuntu的MySQL2.ubuntu忘记mysql的root密码时的操作 1.无法远程连接Ubuntu的MySQL (1) 需要检查防火墙状态 > sudo ufw status #如果防火墙开启的情况&#xff0c;添加规则&#xff1a;允许3306端口开启 > sudo ufw allow 3306 (2) 需要…

计算机网络_1.6.3 计算机网络体系结构分层思想举例

1.6.3 计算机网络体系结构分层思想举例 1、实例引入&#xff08;用户在主机中使用浏览器访问web服务器&#xff09;2、从五层原理体系结构的角度研究该实例3、练习题 笔记来源&#xff1a; B站 《深入浅出计算机网络》课程 本节通过一个常见的网络应用实例&#xff0c;来介绍计…

【论文阅读笔记】Advances in 3D Generation: A Survey

Advances in 3D Generation: A Survey 挖个坑&#xff0c;近期填完摘要 time&#xff1a;2024年1月31日 paper&#xff1a;arxiv 机构&#xff1a;腾讯 挖个坑&#xff0c;近期填完 摘要 生成 3D 模型位于计算机图形学的核心&#xff0c;一直是几十年研究的重点。随着高级神经…

计算机设计大赛 深度学习+opencv+python实现昆虫识别 -图像识别 昆虫识别

文章目录 0 前言1 课题背景2 具体实现3 数据收集和处理3 卷积神经网络2.1卷积层2.2 池化层2.3 激活函数&#xff1a;2.4 全连接层2.5 使用tensorflow中keras模块实现卷积神经网络 4 MobileNetV2网络5 损失函数softmax 交叉熵5.1 softmax函数5.2 交叉熵损失函数 6 优化器SGD7 学…

H5 加密(MD5 Base64 sha1)

1. 说明 很多的时候是避免不了注册登录这一关的&#xff0c;但是一般的注册是没有任何的难度的&#xff0c;无非就是一些简单的获取用户输入的数据&#xff0c;然后进行简单的校验以后调用接口&#xff0c;将数据发送到后端&#xff0c;完成一个简单的注册的流程&#xff0c;那…

python的进程,线程、协程

python进程的实现 #coding:utf-8 from multiprocessing import Process import timedef run(name):print(%s is running % name)time.sleep(3)print(%s finished his run % name)if __name__ __main__:p Process(targetrun, args(XWenXiang,)) # 创建一个进程对象p.start()…

Jvm FullGC 如何排查?

使用场景 我们在使用系统时&#xff0c;有时请求和响应会变得特别慢&#xff0c;系统也变得很卡。 有可能是FullGC的问题&#xff0c;可以逐步地进行排查。 使用jps和top确定进程号pid jps可以列出正在运行的jvm进程&#xff0c;并显示jvm执行主类名称( main()函数所在的类…

Android Button background 失效

问题 Android Button background 失效 详细问题 笔者开发Android项目&#xff0c;期望按照 android:background中所要求的颜色展示。 实际显示按照Android 默认颜色展示 解决方案 将xml的Button 组件修改为<android.widget.Button> 即将代码 <Buttonandroid:l…

oracle数据库慢查询SQL

目录 场景&#xff1a; 环境&#xff1a; 慢SQL查询一&#xff1a; 问题一&#xff1a;办件列表查询慢 分析&#xff1a; 解决方法&#xff1a; 问题二&#xff1a;系统性卡顿 分析&#xff1a; 解决方法&#xff1a; 慢SQL查询二 扩展&#xff1a; 场景&#xff1a; 线…

用Audio2Face导出Unity面部动画

开始之前说句话&#xff0c;新年前最后一篇文章了 一定别轻易保存任何内容&#xff0c;尤其是程序员不要轻易Ctrl S 在A2F去往Unity的路上&#xff0c;还要经历特殊Blender&#xff0c;自己电脑中已下载好的可能不是很好使。 如果想查看UE相关的可以跳转到下边这两篇链接 1. …

【51单片机】LED的三个基本项目(LED点亮&LED闪烁&LED流水灯)(3)

前言 大家好吖&#xff0c;欢迎来到 YY 滴单片机系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过单片机的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; YY的《C》专栏YY的《C11》专栏YY的…

瑞_23种设计模式_工厂模式

文章目录 1 什么是工厂模式案例案例代码 2 简单工厂模式&#xff08;Simple Factory&#xff09;2.1 简单工厂模式的结构2.2 案例改进——简单工厂模式2.3 案例改进代码实现2.4 简单工厂模式优缺点2.5 拓展——静态工厂 3 工厂方法模式&#xff08;Factory Method&#xff09;★…

两个重要极限【高数笔记】

【第一个&#xff1a;lim &#xff08;sinx / x&#xff09; 1, x -- > 0】 1.本质&#xff1a; lim &#xff08;sin‘&#xff1f;’ / ‘&#xff1f;’&#xff09; 1, ‘&#xff1f;’ -- > 0&#xff1b;保证‘&#xff1f;’ -- > 0,与趋向无关 2.例题&#x…

gtkmm xml ui 例子(from string)

文章目录 前言来看一个从字符串中生成UI的例子 前言 glade生成的xml格式不被gtkmm4支持, 需要作修改 来看一个从字符串中生成UI的例子 #include <gtkmm/application.h> #include <gtkmm.h> #include <iostream> using namespace std;class ExampleWindow :…

Cesium DC-SDK集成iconfont阿里矢量图标

Cesium DC-SDK集成iconfont阿里矢量图标 Cesium通过集成iconfont阿里矢量图标&#xff0c;实现自定义图标颜色设置&#xff0c;具体操作如下&#xff1a; 一、引入阿里图标库 1、 通过链接的方式引入到项目中 在项目中引入方式 import url("//at.alicdn.com/t/c/font_…

ONLYOFFICE:一站式办公,探索高效办公新境界

写在前面ONLYOFFICE 介绍ONLYOFFICE 有哪些优势ONLYOFFICE 文档 8.0 发布如何体验 ONLYOFFICEONLYOFFICE 文档部分页面截图 写在前面 在当今这样一个数字化时代&#xff0c;办公软件已经成为我们日常工作中不可或缺的一部分&#xff0c;熟练使用 Office、WPS、腾讯文档、金山文…

前端学习第4天

一、复合选择器 1.后代选择器 2.子代选择器 3.并集选择器 4.交集选择器 5.伪类选择器 1.伪类-超链接&#xff08;拓展&#xff09; 二、CSS特性 1.继承性 body放在style中 2.层叠性 3.优先级 属性 !important;&#xff08;最高优先级&#xff09; 1.优先级-叠加计算规则 2.em…

深度学习介绍

对于具备完善业务逻辑的任务&#xff0c;大多数情况下&#xff0c;正常的人都可以给出一个符合业务逻辑的应用程序。但是对于一些包含超过人类所能考虑到的逻辑的任务&#xff0c;例如面对如下任务&#xff1a; 编写一个应用程序&#xff0c;接受地理信息、卫星图像和一些历史…