目录-入口-由此开始-大纲-总览-概括-枢纽-指导-指引-总领
相关概念:
记录:
一个数据元素称为一个记录, 一个记录通常有多个关键字
多种顺序
按照不同关键字可以排序出不同的序列
排序的稳定性:
对某个排序, 对key相等的记录之间的相对位置, 如果排序前后相对位置不变, 则称该排序为稳定排序, 否则为不稳定排序
排序的分类
按数据存储位置分类
- 内排序: 对内存中的记录进行排序
- 外排序: 对外部存储中的数据进行排序
按原理本质分类
一些常用的排序算法
冒泡排序算法：
child::冒泡排序 算法
选择排序法：
child::选择排序法 算法
插入排序法：
child::直接插入排序 算法
希尔排序法
child::希尔排序法 算法
归并排序
child::归并排序 算法
快速排序
child::快速排序算法
堆排序
child::堆排序 算法
计数排序
child::计数排序算法
不常用的排序算法
- child::基数排序
排序算法总结
复杂度以及稳定性的比较
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 简单选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 直接插入排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(nlogn) ~ O(n²) | O(n1.5) | O(n²) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n²) | O(logn)~O(n) | 不稳定 |
常用的两种稳定排序算法:
- 插入排序
- 速度慢, 数据量小
- 归并排序
- 速度快, 数据量大
效率高的排序算法四大头:
- 希尔排序
- 堆排序
- 归并排序
- 稳定排序
- 快速排序