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

排序第二课【选择排序】直接选择排序 与 堆排序

目录

1. 排序的概念:

2.选择排序的基本思想

3.直接选择排序

4.堆排序


1. 排序的概念:

排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定。

内部排序:数据元素全部放在内存中的排序。

外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。

2.选择排序的基本思想

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

3.直接选择排序

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

选择排序图解:这张动图是选择后面最小的数与前面做交换

当让我们还可以优化,如果是升序,每一次遍历分别选出最小的元素和最大的元素,分别与前面和后面数据做交换。

代码实现:

//交换函数
void Swap(int* p1, int* p2)
{int t = *p1;*p1 = *p2;*p2 = t;
}// 选择排序 升序
void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int maxi = begin;int mini = begin;for (int i = begin; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}Swap(&arr[mini], &arr[begin]);if (begin == maxi){maxi = mini;}Swap(&arr[maxi], &arr[end]);begin++;end--;}
}

直接选择排序的特性总结:

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

4.堆排序

我们这里需要先了解堆的结构,如果不了解可以看我之前的文章【数据结构】这堆是什么。

当我们了解完堆的结构后,我们就可以开始学习堆排序了。 

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的
种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆

  1. 首先要构建一个堆,
  2. 然后让堆顶元素与最后一个元素交换,把最后一个位置元素当作不在堆内。
  3. 然后通过向下调整法调整堆。循环就可以排序

图解:

 建堆可以使用向上调整法建堆和向下调整法建堆,这两种方法在【数据结构】这堆是什么 中有详细讲解。向上调整法建堆时间复杂度为O(N*logN),但是向下调整法时间复杂度低,为O(N)。所以我们这里使用向下调整法建堆。

代码实现:

//向下调整法
void AdjustDown(int* arr, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && arr[child + 1] > arr[child]){child++;}if (arr[parent] < arr[child]){Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//堆排序
void HeapSort(int* arr, int n)
{//建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, n, i);}//排序int end = n - 1;while (end > 0){Swap(&arr[end], &arr[0]);AdjustDown(arr, end, 0);end--;}
}

堆排序的特性总结:

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

本篇文章结束,我们下一篇文章来学习一下:【交换排序】冒泡排序与快速排序。

http://www.lryc.cn/news/114057.html

相关文章:

  • 【chrome扩展开发】vue-i18n使用问题及解决方案
  • 【Vue3】localStorage读取数组并赋值的问题
  • 华为harmonyos4.0鸿蒙4.0安装谷歌服务框架Play商店,解决从服务器检索信息时出错
  • pcl 滤波
  • 前端js--旋转幻灯片
  • 解决mvn clean install遇到testng单元测试失败时打包也失败的问题
  • RISC-V基础之函数调用(二)栈与寄存器(包含实例)
  • 解析器模式(C++)
  • 电子元器件选型与实战应用—02 电容选型第1篇(8000字)
  • 试图将更改推送到 GitHub,但是远程仓库已经包含了您本地没有的工作(可能是其他人提交的修改)
  • Lamport向量时钟算法的C++实现:在分布式系统中生成事件的部分排序并检测因果关系违规
  • 多个excel的sheet合并到一个excel下
  • 【Fegin技术专题】「原生态」打开Fegin之RPC技术的开端,你会使用原生态的Fegin吗?(中)
  • leetcode--每日一题--822--344(使用异或来进行数据交换)
  • OpenStreetMap数据转3D场景【Python + PostgreSQL】
  • 动力节点|MyBatis入门实战到深入源码
  • 分布式规则引擎框架的设计
  • C#开发FFMPEG例子(API方式) FFmpeg推送udp组播流
  • nvm下载node导致npm报错无法使用
  • LeetCode 热题 100JavaScript--2. 两数相加
  • zookeeper总结
  • 【程序环境与预处理玩转指南】
  • 搭建简易syslog日志中转服务器
  • MongoDB文档-进阶使用-spring-boot整合使用MongoDB---MongoRepository完成增删改查
  • 什么是线程局部变量?
  • Jmeter响应中的乱码问题
  • MongoDB文档-进阶使用-MongoDB索引-createindex()与dropindex()-在MongoDB中使用正则表达式来查找
  • CentOS下ZLMediaKit的可视化管理网站MediaServerUI使用
  • 回归预测 | MATLAB实现POA-CNN-BiGRU鹈鹕算法优化卷积双向门控循环单元多输入单输出回归预测
  • Rust 原生支持龙架构指令集