Java教程

数据结构期末复习-各种排序算法的特点

本文主要是介绍数据结构期末复习-各种排序算法的特点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 插入排序
    • 基本思想
    • 不同实现方法导致不同的算法描述
    • 直接插入排序
      • 排序过程
      • 算法分析
    • 折半插入排序
      • 排序过程
      • 算法分析
    • 希尔排序
      • 基本思想
      • 技巧
      • 优点
      • 例如
      • 算法分析
      • 缺点
  • 交换排序
      • 基本思想
    • 起泡排序
      • 基本思想
      • 优点
      • 算法分析
    • 快速排序
      • 基本思想
      • 算法分析
  • 选择排序
      • 基本思想
    • 简单选择排序
      • 排序过程
      • 算法分析
    • 树形选择排序
    • 堆排序
      • 什么是堆
      • 大根堆、小根堆
      • 基本思想
      • 算法分析
  • 归并排序
      • 归并:将两个或两个以上的有序表组合成一个新有序表
    • 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)
是一种稳定的排序方法

快速排序

基本思想

  1. 任取一个元素 (如第一个) 为中心
  2. 所有比它小的元素一律前放,比它大的元素一律后放,形成左右两个子表;
  3. 对各子表重新选择中心元素并依此规则调整,直到每个子表的元素只剩一个

算法分析

时间复杂度: O(n log₂n )
每趟确定的元素呈指数增加

空间复杂度: O(log₂n)
递归要用到栈空间

不稳定–可选任一元素为支点

选择排序

基本思想

每一趟在后面 n-i +1个中选出关键码最小的对象, 作为有序序列的第 i 个记录

简单选择排序

排序过程

在这里插入图片描述
在这里插入图片描述

算法分析

时间复杂度: O(n²)
空间复杂度 :O(1)
稳定

树形选择排序

简单选择排序没有利用上次选择的结果,是造成速度慢的重要原因。如果,能够加以改进,将会提高排序的速度。

在这里插入图片描述

堆排序

什么是堆

在这里插入图片描述
在这里插入图片描述

大根堆、小根堆

在这里插入图片描述

基本思想

  1. 将无序序列建成一个堆
  2. 输出堆顶的最小(大)值
  3. 使剩余的n-1个元素又调整成一个堆,则可得到n个元素的次小值
  4. 重复执行,得到一个有序序列

算法分析

时间复杂度 :O(n log₂n)
空间复杂度 :O(1)
稳定性: 不稳定
适用于n较大的情况

归并排序

归并:将两个或两个以上的有序表组合成一个新有序表

2-路归并排序

排序过程

  1. 初始序列看成n个有序子序列,每个子序列长度为1
  2. 两两合并,得到 [ n/2 ] 个长度为2或1的有序子序列
  3. 再两两合并,重复直至得到一个长度为n的有序序列为止

在这里插入图片描述

算法分析

时间效率 :O(n log₂n)
空间效率 :O(n)
稳定性 :稳定

基数排序

多关键字排序

最高位优先MSD

  1. 先对最高位关键字k1(如花色)排序,将序列分成若干子序列,每个子序列有相同的k1值
  2. 然后让每个子序列对次关键字k2(如面值)排序,又分成若干更小的子序列
  3. 依次重复,直至就每个子序列对最低位关键字kd排序,就可以得到一个有序的序列

最低位优先LSD

  1. 首先依据最低位排序码Kd对所有对象进行一趟排序
  2. 再依据次低位排序码Kd-1对上一趟排序结果排序
  3. 依次重复,直到依据排序码K1最后一趟排序完成,就可以得到一个有序的序列

链式基数排序

先决条件

知道各级关键字的主次关系
知道各级关键字的取值范围

利用分配和收集进行排序过程

  1. 首先对低位关键字排序,各个记录按照此位关键字的值‘分配’到相应的序列里。
  2. 按照序列对应的值的大小,从各个序列中将记录‘收集’,收集后的序列按照此位关键字有序。
  3. 在此基础上,对前一位关键字进行排序。

算法分析

n个记录
每个记录有 d 位关键字
关键字取值范围rd(如十进制为10)
重复执行d趟“分配”与“收集”
每趟对 n 个记录进行“分配”,对rd个队列进行“收集”
需要增加n+2rd个附加链接指针。

时间效率:O(d( n+rd))
空间效率:O(n+rd)
稳 定 性:稳定

这篇关于数据结构期末复习-各种排序算法的特点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!