排序特点总结
稳定性
不稳定排序
| 名称 | 时间 |
|---|---|
| 选择排序 | O(n2) |
| 快速排序 | O(nlogn) 最坏情况O(n2) |
| 堆排序 | O(nlogn) 最坏O(nlog2n) 额外空间的复杂度为O(1) |
| 希尔排序 | O(nlogn) |
| 基数排序 | O(n·k); 需要 O(n) 额外存储空间 （K为特征个数） |
稳定排序
| 名称 | 时间 |
|---|---|
| 插入排序 | O(n2) |
| 冒泡排序 | O(n2) |
| 归并排序 | O(nlogn); 需要 O(n) 额外存储空间 |
| 二叉树排序 | O(nlogn); 需要 O(n) 额外存储空间 |
| 计数排序 | O(n+k); 需要 O(n+k) 额外存储空间，k为序列中Max-Min+1 |
| 桶排序 | O(n); 需要 O(k) 额外存储空间 |
- 比较次数与序列初始状态无关的排序: 选择排序、二分插入排序。
- 快排在完全无序的情况下效果最好O(nlogn)、在有序情况下最差O(n^2)。