【408数据结构与算法】—排序（十四）

【408数据结构与算法】—排序（十四）

一、什么是排序

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

二、排序的应用

三、排序方法的分类

• 按数据存储介质分类：内部排序和外部排序
• 按比较个数：串行排序和并行排序
• 按主要操作：比较排序和基数排序
• 按辅助空间：原地排序和非原地排序
• 按稳定性：稳定排序和非稳定排序
• 按自然性：自然排序和非自然排序

1️⃣按存储介质分为

• 内部排序：数据量不大，数据在内存，无需内外存交换数据
• 外部排序：数据量大，数据在外存（文件排序）

• 外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂的多。

2️⃣按比较器个数分为

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

3️⃣按主要操作分类

• 比较排序：用比较的方法（插入排序、交换排序、选择排序、归并排序）
• 基数排序：不比较元素的大小，仅仅是根据元素本身的取值确定其有序位置

4️⃣按辅助空间可以分为：

• 原地排序：辅助空间用量为O(1)的排序方法（所占的辅助存储空间与参加排序的数据量大小无关）
• 非原地排序：辅助空间用量超过O(1)的排序方法

5️⃣按稳定性可分为

• 稳定排序：能够使任何数值相等的元素，排序以后相对次序不变
• 非稳定排序：不是稳定排序的方法

排序的稳定性只对结构类型的数据排序有意义

6️⃣按自然性分为：

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

四、按排序依据原则

• 插入排序：直接插入排序、折半插入排序、希尔排序
• 交换排序：冒泡排序、快速排序
• 选择排序:简单选择排序、堆排序
• 归并排序：2路归并排序
• 基数排序

五、那排序所需的工作量

六、存储结构—记录序列以顺序表存储