排序算法总结
常用排序算法
| 时间复杂度 | 空间复杂度 | 是否为稳定排序 | 是否为原地排序 | |
|---|---|---|---|---|
| 直接插入排序 | $O(n^2)$ | $O(1)$ | ✔ | ✔ |
| 折半插入排序 | $ O(n^2)$ (只优化了比较的过程) | $O(1)$ | ✔ | ✔ |
| 希尔排序 | 和增量有关，最坏$O(n^2)$ | $O(1)$ | ❌ | ✔ |
| 冒泡排序 | $O(n^2)$ | $O(1)$ | ✔ | ✔ |
| 快速排序 | $O(nlog_2n)$ | $O(log_2n)$ | ❌ | ✔ |
| 简单选择排序 | $O(n^2)$ | $O(1)$ | ❌ | ✔ |
| 堆排序 | $O(nlog_2n)$ | $O(1)$ | ❌ | ✔ |
| 归并排序 | $O(nlog_2n)$ | $O(n)$ | ✔ | ❌ |
| ==基数排序== | $O(dn) d是位数$ | $O(d)$ | ✔ | ❌ |
| ==桶排序== | $O(n+k)$ k为桶个数，n为元素数量 | $O(n+k)$ | ✔ | ❌ |
References
- 严版数据结构
- 数据结构与算法之美
