【408数据结构与算法】—排序（十四）
一、什么是排序
排序：将一组杂乱无章的数据按一定规律排列起来。即将无序序列排列成一个有序序列（由小到大或由大到小）的运算。如果参加排序的数据结点包含多个数据域，那么排序往往是针对其中某个域而言的。
二、排序的应用
三、排序方法的分类
- 按数据存储介质分类：内部排序和外部排序
- 按比较个数：串行排序和并行排序
- 按主要操作：比较排序和基数排序
- 按辅助空间：原地排序和非原地排序
- 按稳定性：稳定排序和非稳定排序
- 按自然性：自然排序和非自然排序
1️⃣按存储介质分为
- 内部排序：数据量不大，数据在内存，无需内外存交换数据
- 外部排序：数据量大，数据在外存（文件排序）
- 外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂的多。
2️⃣按比较器个数分为
- 串行排序：单处理机（同一时刻比较一对元素）
- 并行排序：多处理机（同一时刻比较多对元素）
3️⃣按主要操作分类
- 比较排序：用比较的方法（插入排序、交换排序、选择排序、归并排序）
- 基数排序：不比较元素的大小，仅仅是根据元素本身的取值确定其有序位置
4️⃣按辅助空间可以分为：
- 原地排序：辅助空间用量为O(1)的排序方法（所占的辅助存储空间与参加排序的数据量大小无关）
- 非原地排序：辅助空间用量超过O(1)的排序方法
5️⃣按稳定性可分为
- 稳定排序：能够使任何数值相等的元素，排序以后相对次序不变
- 非稳定排序：不是稳定排序的方法
排序的稳定性只对结构类型的数据排序有意义
6️⃣按自然性分为：
- 自然排序：输入数据越有序，排序的速度越快的排序方法
- 非自然排序：不是自然排序的方法
四、按排序依据原则
- 插入排序：直接插入排序、折半插入排序、希尔排序
- 交换排序：冒泡排序、快速排序
- 选择排序:简单选择排序、堆排序
- 归并排序：2路归并排序
- 基数排序
五、那排序所需的工作量
六、存储结构—记录序列以顺序表存储
