数据结构期末复习-各种排序算法的特点
2021/7/2 11:51:25
本文主要是介绍数据结构期末复习-各种排序算法的特点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 插入排序
- 基本思想
- 不同实现方法导致不同的算法描述
- 直接插入排序
- 排序过程
- 算法分析
- 折半插入排序
- 排序过程
- 算法分析
- 希尔排序
- 基本思想
- 技巧
- 优点
- 例如
- 算法分析
- 缺点
- 交换排序
- 基本思想
- 起泡排序
- 基本思想
- 优点
- 算法分析
- 快速排序
- 基本思想
- 算法分析
- 选择排序
- 基本思想
- 简单选择排序
- 排序过程
- 算法分析
- 树形选择排序
- 堆排序
- 什么是堆
- 大根堆、小根堆
- 基本思想
- 算法分析
- 归并排序
- 归并:将两个或两个以上的有序表组合成一个新有序表
- 2-路归并排序
- 排序过程
- 算法分析
- 基数排序
- 多关键字排序
- 最高位优先MSD
- 最低位优先LSD
- 链式基数排序
- 先决条件
- 利用分配和收集进行排序过程
- 算法分析
插入排序
基本思想
每步将一个待排序的对象,按其关键码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。
即边插入边排序,保证子序列中随时都是排好序的
不同实现方法导致不同的算法描述
直接插入排序—基于顺序查找
折半插入排序—基于折半查找
希尔排序—基于逐趟缩小增量
直接插入排序
排序过程
整个排序过程为n-1趟插入,即先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序。
算法分析
时间复杂度:O(n²)
空间复杂度:O(1)
是一种稳定的排序方法
折半插入排序
排序过程
它所需要的关键码比较次数与待排序对象序列的初始排列无关,仅依赖于对象个数。在插入第 i 个对象时,需要经过 [ log₂i ] +1 次关键码比较,才能确定它应插入的位置 。
算法分析
时间复杂度: O(n²)
空间复杂度:O(1)
是一种稳定的排序方法
- 减少了比较次数,但没有减少移动次数
- 平均性能优于直接插入排序
希尔排序
基本思想
先将整个待排记录序列分割成若干子序列,分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。
技巧
子序列的构成不是简单地“逐段分割”将相隔某个增量dk的记录组成一个子序列让增量dk逐趟缩短(例如依次取5,3,1)直到dk=1为止。
优点
小元素跳跃式前移,最后一趟增量为1时,序列已基本有序。平均性能优于直接插入排序
例如
算法分析
时间复杂度时n和d的函数
O(n1.25)~O(1.6n1.25) --经验公式
空间复杂度:O(1)
是一种不稳定的排序方法
缺点
- 如何选择最佳d序列,目前尚未解决
- 最后一个增量值必须为1,无除1以外的公因子
- 不宜在链式存储结构上实现
交换排序
基本思想
两两比较,如果发生逆序则交换,直到所有记录都排好序为止。
起泡排序O(n²)
快速排序O(n log₂n)
起泡排序
基本思想
每趟不断将记录两两比较,并按“前小后大” 规则交换
优点
每趟结束时,不仅能挤出一个最大值到最后面位置,还能同时部分理顺其他元素
一旦下趟没有交换,还可提前结束排序
算法分析
时间复杂度: O(n²)
空间复杂度: O(1)
是一种稳定的排序方法
快速排序
基本思想
- 任取一个元素 (如第一个) 为中心
- 所有比它小的元素一律前放,比它大的元素一律后放,形成左右两个子表;
- 对各子表重新选择中心元素并依此规则调整,直到每个子表的元素只剩一个
算法分析
时间复杂度: O(n log₂n )
每趟确定的元素呈指数增加
空间复杂度: O(log₂n)
递归要用到栈空间
不稳定–可选任一元素为支点
选择排序
基本思想
每一趟在后面 n-i +1个中选出关键码最小的对象, 作为有序序列的第 i 个记录
简单选择排序
排序过程
算法分析
时间复杂度: O(n²)
空间复杂度 :O(1)
稳定
树形选择排序
简单选择排序没有利用上次选择的结果,是造成速度慢的重要原因。如果,能够加以改进,将会提高排序的速度。
堆排序
什么是堆
大根堆、小根堆
基本思想
- 将无序序列建成一个堆
- 输出堆顶的最小(大)值
- 使剩余的n-1个元素又调整成一个堆,则可得到n个元素的次小值
- 重复执行,得到一个有序序列
算法分析
时间复杂度 :O(n log₂n)
空间复杂度 :O(1)
稳定性: 不稳定
适用于n较大的情况
归并排序
归并:将两个或两个以上的有序表组合成一个新有序表
2-路归并排序
排序过程
- 初始序列看成n个有序子序列,每个子序列长度为1
- 两两合并,得到 [ n/2 ] 个长度为2或1的有序子序列
- 再两两合并,重复直至得到一个长度为n的有序序列为止
算法分析
时间效率 :O(n log₂n)
空间效率 :O(n)
稳定性 :稳定
基数排序
多关键字排序
最高位优先MSD
- 先对最高位关键字k1(如花色)排序,将序列分成若干子序列,每个子序列有相同的k1值
- 然后让每个子序列对次关键字k2(如面值)排序,又分成若干更小的子序列
- 依次重复,直至就每个子序列对最低位关键字kd排序,就可以得到一个有序的序列
最低位优先LSD
- 首先依据最低位排序码Kd对所有对象进行一趟排序
- 再依据次低位排序码Kd-1对上一趟排序结果排序
- 依次重复,直到依据排序码K1最后一趟排序完成,就可以得到一个有序的序列
链式基数排序
先决条件
知道各级关键字的主次关系
知道各级关键字的取值范围
利用分配和收集进行排序过程
- 首先对低位关键字排序,各个记录按照此位关键字的值‘分配’到相应的序列里。
- 按照序列对应的值的大小,从各个序列中将记录‘收集’,收集后的序列按照此位关键字有序。
- 在此基础上,对前一位关键字进行排序。
算法分析
n个记录
每个记录有 d 位关键字
关键字取值范围rd(如十进制为10)
重复执行d趟“分配”与“收集”
每趟对 n 个记录进行“分配”,对rd个队列进行“收集”
需要增加n+2rd个附加链接指针。
时间效率:O(d( n+rd))
空间效率:O(n+rd)
稳 定 性:稳定
这篇关于数据结构期末复习-各种排序算法的特点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)