排序
排序后，使得元素是 递增 或 递减 的关系
排序分类
| 基础排序 | 升级排序 | |
|---|---|---|
| 插入类排序 | 直接插入排序 | 希尔排序 |
| 交换类排序 | 冒泡排序 | 快速排序 |
| 选择类排序 | 直接选择排序 | 堆排序 |
算法比较
算法的选择
在选取排序方法时，需要考虑的因素有：
- 待排序的元素个数
- 元素本身的大小，如：
0-99就比较小，1000-9999相对较大 - 关键字的分布情况，如：基本有序
- 对排序稳定性的要求
- 语言工具的条件
- 辅助空间的大小
序列的元素 数量较小
可采用：
- 直接插入排序
- 简单选择排序
原因：数量小，算法简单
记录本身信息量大时
用 简单选择排序 方法较好
原因：由于 直接插入排序 所需的记录移动操作，比 简单选择排序 多
序列的元素 基本有序
可采用：
- 直接插入排序，算法本身快
- 冒泡排序（因为基本有序，不需要交换位置）
序列的元素 数量很大，关键字位数较少时
采用 基数排序 较好
关键字位数较少：比如 最大元素是 99，2位数
原因：最大数是 n 位数，使用基数排序就需要执行 n 趟
序列的元素 数量很多
应采用时间复杂度为 O(nlog₂n) 的排序方法：
快速排序：目前被认为是内部排序中最好的方法，当待排序的关键字为随机分布时，快速排序的平均运行时间最短
堆排序：只需要一个辅助空间，并且不会出现在快速排序中可能出现的最快情况。
归并排序：
快速排序和堆排序都是 不稳定 的排序方法，若要求 排序稳定，可选择归并排序