文章目录

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