0 知识回顾

1 排序的基本概念

什么是排序？

• 排序：将一组杂乱无章的数据按一定规律顺次排列起来。即，将无序序列排成一个有序序列（由小到大或由大到小）的运算。
• 如果参加排序的数据结点包含多个数据域，那么排序往往是针对其中某个域而言。

1.1 方法分类

按存储介质可分为：

• 内部排序：数据量不大、数据在内存(RAM)，无需内外存交换数据
• 外部排序：数据量较大、数据在外存(文件排序)

按比较器个数可分为：

• 串行排序：单处理机（同一时刻比较一对元素）
• 并行排序：多处理机（同一时刻比较多对元素）

按主要操作可分为：

• 比较排序：用比较的方法

插入排序、交换排序、选择排序、归并排序

• 基数排序：不比较元素的大小，仅仅根据元素本身的取值确定其有序位置

按辅助空间可分为：

• 原地排序：辅助空间用量为$O(1)$的排序方法

(所占的辅助存储空间与参加排序的数据量大小无关)

• 非原地排序：辅助空间用量超过$O(1)$的排序方法

按稳定性可分为：

• 稳定排序：能够使任何数值柚等的元素排序以相对次序（位置）不变的
• 非稳定性排序：不是稳定排序的方法

示例1的相对位置没发生改变，所以是稳定排序；示例2相对位置发生改变，所以是不稳定排序。

按自然性可分为：

• 自然排序：输入数据越有序，排序的速度越快的排序方法
• 非自然排序：不是自然排序的方法

按排序依据原则：

1.2 存储结构

1.2.1 以顺序表存储