排序基本概念
排序（Sorting）是指将一个数据元素的任意序列重新排列成按关键字有序的序列。
稳定性
在排序过程中，若干记录的关键字相等。排序前后含相等关键字的记录的相对位置保持不变，则为稳定的，否则为不稳定的。
内排序与外排序
- 内部排序：排序过程中只使用计算机内存存放记录
- 外部排序：除内存外还需要借助外存，快慢取决于内外存之间的数据交换次数
内部排序的分类
内部排序基于不同的扩大有序序列长度的方式，大致分为：
| 类别 | 特点 | 代表算法 |
|---|---|---|
| 插入类 | 将无序序列的记录插入有序序列 | 直接插入、折半插入、希尔 |
| 交换类 | 交换记录得到最大/最小关键字并加入有序序列 | 冒泡、快速 |
| 选择类 | 从无序序列中选择最大/最小记录加入有序序列 | 简单选择、树形选择、堆排序 |
| 归并类 | 归并两个以上有序子序列 | 归并排序 |
| 其他 | 不基于比较 | 基数排序 |
算法评价维度
- 基本操作：比较、移动
- 辅助存储空间：除了记录存放外所需的额外空间
- 算法本身复杂度（主要评价指标）
链接到
- 上一个知识点：无（本章第一个知识点）
- 下一个知识点：6.2 直接插入排序