25.选择排序,归并排序,基数排序

目录

一. 选择排序

(1)简单选择排序

(2)堆排序

二. 归并排序

三. 基数排序

四. 各种排序方法的比较

(1)时间性能

(2)空间性能

(3)排序方法的稳定性能

(4)关于“排序方法的时间复杂度的下限”


一. 选择排序

(1)简单选择排序

基本思想:在待排序的数据中选出最大(小)的元素放在其最终的位置。
基本操作:
1.首先通过n-1次关键字比较,从n个记录中找出关键字最小的记录,将它与第一个记录交换。
2.再通过n-2次比较,从剩余的n-1个记录中找出关键字次小的记录,将它与第二个记录交换。
3.重复上述操作,共进行n-1趟排序后,排序结束。

 

 不难写出算法:

void SelectSort(SqList &L){for(i=1; i<L.length; ++i){k=i;  //第i趟从第i个元素开始for(j=i+1; j<=L.length; j++)if(L.r[j].key < L.r[k].key) k=j;  //记录最小值位置if(k!=i)  L.r[i]←—→L.r[k];  //交换}
}

下面我们分析时间复杂度。对移动次数来说,最好情况是0,最坏情况是3(n-1),也就是每一趟都得移动(每次移动需要移动3次)。对比较次数来说,无论待排序列处于什么状态,选择排序所需进行的"比较”次数都相同,为\sum_{i=1}^{n-1}(n-i)=\frac{n}{2}(n-1)

上面的算法是不稳定排序(但是可以稳定化)。具体的说用数组实现的选择排序是不稳定的,用链表实现的选择排序是稳定的。例如,给定8,5,8*,7,9;第1次:5,8,8*,7,9;第2次:5,7,8*,8,9;从而可以验证它是不稳定的。

(2)堆排序

堆的定义:若n个元素的序列{\left \{ a_1,a_2...a_n \right \}}满足\left\{\begin{matrix} a_i\leqslant a_{2i}\\ a_i\leqslant a_{2i+1} \end{matrix}\right.\left\{\begin{matrix} a_i\geqslant a_{2i}\\ a_i\geqslant a_{2i+1} \end{matrix}\right.,则分别称该序列为小根堆和大根堆。从堆的定义可以看出,堆实质是满足如下性质的完全二叉树:二叉树中任一非叶子结点均小于(大于)它的孩子结点。

显然,大根堆的根结点是最大值,小根堆的根结点是最小值。若在输出堆顶的最小值(最大值)后,使得剩余n-1个元素的序列又重建成一个堆,则得到n个元素的次小值(次大值)....如此反复,便能得到一个有序序列,这个过程称之为堆排序

那么怎么重建呢?以小(大)根堆为例:
1.输出堆顶元素之后,以堆中最后一个元素(编号最大的元素)替代之;
2.然后将根结点值与左、右子树的根结点值进行比较,并与其中小(大)者进行交换;
3.重复上述操作,直至叶子结点,将得到新的堆,称这个从堆顶至叶子的调整过程为“筛选”。

例如,对下面的小根堆,把13输出,最后一个元素97作为根结点,它的左右孩子是38和27,27较小,所以把97和27交换。此时97的左右孩子是65和49,49较小,把49和97交换,这个时候97已经是叶子结点就不用再操作了。

 写出算法如下:

void HeapAdjust(elem R[], int s, int m){
/*已知R[s..m]中记录的关键字除R[s]之外均满足堆的定义,本函数调整R[s]的关键字,使R[s..m]成为一个大根堆*/rc = R[s];for (j=2*s; j<=m; j *= 2){  //沿key较大的孩子结点向下筛选if (j < m && R[j] < R[j+1]) ++j;  //j为key较大的记录的下标if (rc >= R[j]) break;  //rc大于左右孩子,这个时候已经符合要求,就不用做了R[s] = R[j];  //较大的孩子结点往上升s = j;  //rc应插入在位置s上,更新s}//forR[s] = rc;  //插入
}//HeapAdjust

HeapAdjust函数是一个用于调整堆的函数。它接受一个数组R,以及两个整数s和m作为参数。s表示要调整的子树的根节点的位置,m表示该子树的最后一个节点的位置。

首先,将根节点的值保存在变量rc中。然后,通过一个循环来比较根节点和其子节点的值。在循环中,变量j初始化为根节点的左子节点的位置(2*s),然后每次乘以2,即可得到下一个子节点的位置。在循环中,首先判断是否存在右子节点,并且右子节点的值是否大于左子节点的值。如果满足条件,则将j加1,即将j指向右子节点。然后,判断rc的值是否大于等于R[j]的值。如果满足条件,则退出循环。如果rc的值小于R[j]的值,则将R[j]的值赋给R[s],即将较大的子节点的值上移到根节点的位置。然后,将s更新为j,即将s指向较大子节点的位置。循环结束后,将rc的值赋给R[s],即将根节点的值放到合适的位置上。这样,HeapAdjust函数完成了对以s为根节点的子树的调整,使其满足堆的性质。

可以看出:对一个无序序列反复“筛选”就可以得到一个堆。即:从一个无序序列建堆的过程就是一个反复“筛选”的过程。我们重新考察堆的定义,显然:单结点的二叉树是堆,在完全二叉树中所有以叶子结点(序号i > n/2,这里是整除向下取整)为根的子树也是堆。这样,我们只需依次将以序号为n/2,n/2 - 1,.....1的结点为根的子树均调整为堆即可。即:对应由n个元素组成的无序序列,“筛选”只需从第n/2个元素开始。

由于堆实质上是一个线形表,那么我们可以顺序存储一个堆。下面以一个实例介绍建一个小根堆的过程。例如给定关键字为49,38,65,97,76,13,27,49的一组记录,将其按关键字调整为一个小根堆:

将初始无序的R[1]到R[n]建成一个小根堆,可用以下语句实现:

for(i = n/2 ; i >= 1; i--)HeapAdjust (R, i, n);

上面我们了解了怎么建堆。若对一个无序存列建堆,然后输出根。重复该过程就可以由一个无需序列输出有序序列。实质上,堆排序就是利用完全二叉树中父结点与孩子结点之间的内在关系来排序的。

void HeapSort(elem R[]){  //对R[1]到R[n]进行堆排序int i;for (i = n/2; i>= 1; i--)HeapAdjust(R, i, n);//建初始堆for (i = n; i > 1; i--){  //进行n-1趟排序Swap(R[1], R[i]);  //根与最后一个元素交换,也就是把根结点输出并放在最后一个位置HeapAdjust(R, 1, i-1);  //对R[1]到R[i-1]重新建堆}
}//HeapSort

最后我们来研究时间复杂度。初始堆化所需时间不超过O(n),排序阶段(不含初始堆化)每次重新堆化所需时间不超过O(logn),则n-1次循环所需时间不超过O(nlogn)。因此:
Tw(n)=O(n)+ O(nlogn)= O(nlogn)

堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复筛选上。堆排序在最坏情况下,其时间复杂度也为O(nlog2n),这是堆排序的最大优点。无论待排序列中的记录是正序还是逆序排列,都不会使堆排序处于"最好"或"最坏"的状态。另外,堆排序仅需一个记录大小供交换用的辅助存储空间。

然而堆排序是一种不稳定的排序方法,它不适用于待排序记录个数n较少的情况,但对于n较大的文件还是很有效的。

二. 归并排序

基本思想:将两个或两个以上的有序子序列“归并”为一个有序予列。在内部排序中,通常采用的是2-路归并排序。即:将两个位置相邻的有序子序列R[1..m]和R[m+1..n]归并为一个有序序列R[1..n]。

这种树称为归并树。n个元素归并排序只需要\left \lceil log_2n \right \rceil趟。下面讨论怎么把两个有序序列合并成一个有序序列。这里可以参考线性表的合并算法。设R[low]-R[mid]和R[mid+1]-R[high]为相邻,归并成一个有序序列R1[low] - R1[high].

若SR[i].key<=SR[j].key,则TR[k]=RS[i];k++;i++;  否则,TR[k]=SR[j];k++;j++;

归并排序的时间效率是O(nlog2n),空间效率是O(n),因为需要一个与原始序列同样大小的辅助序列(TR)。这正是此算法的缺点。归并排序算法是稳定的算法。

三. 基数排序

基本思想:分配+收集

基数排序也叫桶排序或箱排序:设置若干个箱子,将关键字为k的记录放入第k个箱子,然后在按序号将非空的连接。基数排序的数字是有范围的,均由0-9这十个数字组成,则只需设置十个箱子,相继按个、十、百...进行排序。例:给定待排序序列(614,738,921,485,637,101,215,530,790,306)。这里每一个箱子都是一个队列,遵循先进先出的原则:

至此排序完成!基数排序的时间效率:O(k*(n+m)),其中k:关键字个数(上面有3个关键字),m:关键字取值范围为m个值(上面为10),n:元素个数。这里,每一趟分配n个元素,收集m个桶,总共需要k遍。

空间效率:这里需要放置m个桶,回收的时候回收n个元素,则空间复杂度是O(n+m)。基数排序是稳定的。

四. 各种排序方法的比较

(1)时间性能

1.按平均的时间性能来分,有三类排序方法:

  • 时间复杂度为O(nlogn)的方法有:快速排序、堆排序和归并排序,其中以快速排序为最好;
  • 时间复杂度为O(n^2)的有:直接插入排序、冒泡排序和简单选择排序,其中以直接插入为最好,特别是对那些对关键字近似有序的记录序列尤为如此;
  • 时间复杂度为O(n)的排序方法只有:基数排序。

2.当待排记录序列按关键字顺序有序时,直接插入排序和冒泡排序能达到到O(n)的时间复杂度;而对于快速排序而言,这是最不好的情况,此时的时间性能退化为O(n^2),因此是应该尽量避免的情况。
3.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

(2)空间性能

指的是排序过程中所需的辅助空间大小.
1.所有的简单排序方法(包括:直接插入、冒泡和简单选择)和堆排序的空间复杂度为O(1)
2.快速排序为O(logn),为栈所需的辅助空间
3.归并排序所需辅助空间最多,其空间复杂度为O(n)
4.链式基数排序需附设队列首尾指针,则空间复杂度为O(rd)

(3)排序方法的稳定性能

稳定的排序方法指的是,对于两个关键字相等的记录,它们在序列中的相对位置,在排序之前和经过排序之后,没有改变。

  • 当对多关键字的记录序列进行LSD方法排序时,必须采用稳定的排序方法。
  • 对于不稳定的排序方法,只要能举出一个实例说明即可。
  • 快速排序和堆排序是不稳定的排序方法。

(4)关于“排序方法的时间复杂度的下限”

本章讨论的各种排序方法,除基数排序外,其它方法都是基于“比较关键字”进行排序的排序方法,可以证明,这类排序法可能达到的最快的时间复杂度为O(nlogn)。(基数排序不是基于“比较关键字”的排序方法,所以它不受这个限制)。

可以用一棵判定树来描述这类基于“比较关键字”进行排序的排序方法。

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

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

相关文章

MyBatis查询数据库

文章目录 一.基础概念1.什么是MyBatis2.添加MyBatis依赖3.配置MyBatis中的xml路径 二.MyBatis的使用1.添加用户实体类2.添加 mapper 接⼝3.配置xml4.接口实现5.添加Service6.添加Controller 三.其它情况下Mybatis的使用1.返回自增主键值2.数据库字段和类属性不匹配 四.动态SQL1…

MybatisPlus-Generator

文章目录 一、前言二、MybatisPlus代码生成器1、引入依赖2、编写生成代码3、配置说明3.1、全局配置(GlobalConfig)3.2、包配置(PackageConfig)3.3、模板配置(TemplateConfig)3.4、策略配置(StrategyConfig)3.4.1、Entity 策略配置3.4.2、Controller 策略配置3.4.3、Service 策略…

Ceph IO流程及数据分布

1. Ceph IO流程及数据分布 1.1 正常IO流程图 步骤&#xff1a; client 创建cluster handler。client 读取配置文件。client 连接上monitor&#xff0c;获取集群map信息。client 读写io 根据crshmap 算法请求对应的主osd数据节点。主osd数据节点同时写入另外两个副本节点数据。…

C++ vector

目录 一、vector的介绍及使用 1.1 vector的介绍 1.1.1 认识vector 1.1.2 成员类型​​​​​​​ 1.1.3 成员函数一览 1.1.4 非成员函数重载 1.2 vector的使用 1.2.1 构造、析构与赋值操作符重载 1.2.2 reserve 与 resize 1.2.3 insert、erase 与 find extra train 1. 二叉树的…

工厂人员作业行为动作识别检测算法

工厂人员作业行为动作识别检测算法通过yolov7python深度学习算法框架模型&#xff0c;工厂人员作业行为动作识别检测算法实时识别并分析现场人员操作动作行为是否符合SOP安全规范流程作业标准&#xff0c;如果不符合则立即抓拍告警提醒。Python是一种由Guido van Rossum开发的通…

Nginx详解 三:高级配置

文章目录 1. 网页的状态页2. Nginx第三方模块2.1 echo模块 3. 变量3.1 内置变量3.1.1 示例 3.2 自定义变量3.2.1 自定义访问日志3.2.2 自定义json 格式日志 3.4 Nginx压缩功能 4. HTTPS4.1 Nginx的HTTPS工作原理4.2 启用功能模块的配置过程 5、自定义图标 1. 网页的状态页 基于…

【网络安全防护】上海道宁与Bitdefender帮助您构建弹性网络并降低安全运营成本

在网络的世界中 风险变得更加常见与复杂 企业需要从网络安全转向网络弹性 复杂的网络攻击已非常普遍 在面临攻击时 企业如何保持业务连续性&#xff1f; Bitdefender GravityZone将 风险分析、安全加固、威胁预防 检测和响应功能相结合 帮助您构建弹性网络 并降低安全…

【UE5】虚幻5教程-如何解决场景远处植被没有阴影

没有阴影的远处植被 下面是解决的方法。 首先打开项目设置 项目设置 点击左侧的渲染 渲染 在框内输入“距离”&#xff0c;并选择生成距离场。 光源内添加“定向光源”&#xff0c;如果已有可以忽略。 点击“directional light"并在下方找到"距离场阴影&qu…

go学习part20(1)反射

283_尚硅谷_反射基本介绍和示意图_哔哩哔哩_bilibili 1.介绍 1&#xff09;基本数据类型的类型和类别一致&#xff0c;但是结构体等不一样。 2)反射的例子&#xff08;桥连接&#xff0c;序列化&#xff09; 序列化指定tag&#xff0c;会反射生成tag字符串 3&#xff09;refl…

部署java程序的服务器cpu过高如何排查和解决

1.top命令找到占用CPU高的Java进程PID 2.根据进程ID找到占用CPU高的线程 ps -mp pid -o THREAD,tid | sort -r ps -mp 124682 -o THREAD,tid | sort -r 3.将指定的线程ID输出为16进制格式 printf “%x\n” tid printf "%x\n" 6384 18f0 4.jstack pid |…

一句话画出动漫效果

链接&#xff1a; AI Comic Factory - a Hugging Face Space by jbilcke-hfDiscover amazing ML apps made by the communityhttps://huggingface.co/spaces/jbilcke-hf/ai-comic-factory 选择类型&#xff1a; Japanese 输入提示词&#xff1a; beauty and school love st…

pyechart笔记:opts.AxisOpts

定制化图表的轴线&#xff08;x轴和y轴&#xff09;的样式和设置 0 不设置坐标轴 c1(Bar().add_xaxis([力量,智力,敏捷]).add_yaxis(全能骑士,# 系列名称&#xff0c;用于 tooltip 的显示&#xff0c;legend 的图例筛选。[429,321,296],#系列数据).add_yaxis(猴子,[352,236,4…

开源微服务如何选型?Spring Cloud、Dubbo、gRPC、Istio 详细对比

作者&#xff1a;刘军 不论您是一名开发者、架构师、CTO&#xff0c; 如果您曾深度参与在微服务开发中&#xff0c;那么相信您一定有过开源微服务框架或体系选型的疑问&#xff1a;Apache Dubbo、Spring Cloud、gRPC 以及 Service Mesh 体系产品如 Istio&#xff0c;到底应该选…

【taro react】(游戏) ---- 贪吃蛇

1. 预览 2. 实现思路 实现食物类&#xff0c;食物坐标和刷新食物的位置&#xff0c;以及获取食物的坐标点&#xff1b;实现计分面板类&#xff0c;实现吃食物每次的计分以及积累一定程度的等级&#xff0c;实现等级和分数的增加&#xff1b;实现蛇类&#xff0c;蛇类分为蛇头和…

【状态估计】基于UKF法、AUKF法、EUKF法电力系统三相状态估计研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

IDEA 出现问题:.gitgnore忽略文件失效解决方案

❤️作者主页&#xff1a;小虚竹 ❤️作者简介&#xff1a;大家好,我是小虚竹。Java领域优质创作者&#x1f3c6;&#xff0c;CSDN博客专家&#x1f3c6;&#xff0c;华为云享专家&#x1f3c6;&#xff0c;掘金年度人气作者&#x1f3c6; ❤️技术活&#xff0c;该赏 ❤️点赞…

开始MySQL之路——MySQL安装和卸载

MySQL的介绍 MySQL数据库管理系统由瑞典的DataKonsultAB公司研发&#xff0c;该公司被Sun公司收购&#xff0c;现在Sun公司又被Oracle公司收购&#xff0c;因此MySQL目前属于Oracle旗下产品。 MySQL所使用的SQL语言是用于访问数据库的最常用标准化语言。MySQL软件采用了双授权…

Docsify + Gitalk详细配置过程讲解

&#x1f496; 作者简介&#xff1a;大家好&#xff0c;我是Zeeland&#xff0c;开源建设者与全栈领域优质创作者。&#x1f4dd; CSDN主页&#xff1a;Zeeland&#x1f525;&#x1f4e3; 我的博客&#xff1a;Zeeland&#x1f4da; Github主页: Undertone0809 (Zeeland)&…

Python爬虫(十七)_糗事百科案例

糗事百科实例 爬取糗事百科段子&#xff0c;假设页面的URL是: http://www.qiushibaike.com/8hr/page/1 要求&#xff1a; 使用requests获取页面信息&#xff0c;用XPath/re做数据提取获取每个帖子里的用户头像连接、用户姓名、段子内容、点赞次数和评论次数保存到json文件内…

什么是HTTPS协议?与HTTP协议区别?

一、协议科普 HTTP协议&#xff08;超文本传输协议&#xff09;是一种用于在计算机网络上传输超文本的应用层协议。它是一种客户端-服务器协议&#xff0c;允许客户端通过Web浏览器等方式向服务器发送请求&#xff0c;服务器则返回响应。HTTP协议是构建万维网&#xff08;WWW&…