排序算法比较
| 排序算法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 | 备注 |
|---|---|---|---|---|---|
| 冒泡 | O(n2) | O(n2) | 稳定 | O(1) | n小的时候较好 |
| 交换 | O(n2) | O(n2) | 不稳定 | O(1) | n小的时候较好 |
| 选择 | O(n2) | O(n2) | 不稳定 | O(1) | n小的时候较好 |
| 插入 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已排序时较好 |
| 基数 | O( |
O( |
稳定 | O(1) | R是基数，B是真数 |
| shell | O( |
O(ns) 1<s<2 | 不稳定 | O(1) | s是所选分组 |
| 快速 | O( |
O(n2) | 不稳定 | O( |
n大时较好 |
| 归并 | O( |
O( |
稳定 | O(1) | n大时较好 |
| 堆 | O( |
O( |
不稳定 | O(1) | n大时较好 |
其他
| 算法 | 平均时间 |
|---|---|
| 哈希 | O(1) |
| 二分查找 | O( |
| 二叉搜索树 | O( |
| 线性，遍历 | O(n) |
算法时间复杂度数排序依次：
常数阶O(1) < 对数阶O()
< 线性阶O(n) < 线性对数阶O(n*)
< 平方阶O(n2) < 立方阶O(n3) < k次方阶O(nk) < 指数阶O(2n).......
