选择排序法
插入排序法
冒泡排序法
归并排序法
- 自顶向下
- 自底向上
快速排序法
- 单路快速排序法
- 双路快速排序法
- 三路快速排序法
堆排序法
希尔排序法
- 不同的步长序列
| 方法 | 时间复杂度 | 空间复杂度 | 特殊数据 | 其他 | 稳定性 |
|---|---|---|---|---|---|
| 选择排序法 | O(n^2) | O(1) | 不稳定 | ||
| 插入排序法 | O(n^2) | O(1) | 完全有序数组，时间O(n) | 稳定的(依赖具体实现) | |
| 冒泡排序法 | O(n^2) | O(1) | 完全有序数组，时间O(n) | 稳定的(依赖具体实现) | |
| 归并排序法 | O(nlogn) | O(n) | 完全有序数组，优化之后时间O(n) | O(nlogn)求数组中的逆序对个数 | 稳定的(merge过程中相同元素没机会跳到前面去) |
| 快速排序法 | O(nlogn) * (存在随机期望复杂度) | O(1) | 含有相同元素数组，三路快排时间O(n) | O(n)求解selectK, topK | 不稳定的(随机标定点直接打乱了顺序) |
| 堆排序法 | O(nlogn) | O(1) (优化heapify之后) | 堆；优先队列 O(nlogk)解决selectK, topK问题 | 不稳定的 | |
| 希尔排序法 | O(nlogn)-O(n^2) | O(1) | 分组的思想 | 不稳定(分组数据之间有间隔) |
排序算法的稳定性
- 排序前相等的俩个元素，排序后相对位置不变。一个稳定的排序算法也有可能被实现成不稳定的。
-
如果元素只有一个域，稳定性没有意义。
稳定性
域
