Posted Updated 0 visits
排序算法总结
参考资料
| 冒泡 |
O(n^2) |
O(n) |
O(n^2) |
O(1) |
稳定 |
| 简单选择排序 |
O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
不稳定 |
| 直接插入排序 |
O(n^2) |
O(n) |
O(n^2) |
O(1) |
稳定 |
| 希尔排序 |
O(nlogn) ~ O(n^2) |
O(n1.3) |
O(n^2) |
O(1) |
不稳定 |
| 快速排序 |
O(nlogn) |
O(nlogn) |
O(n^2) |
O(logn)~O(n) |
不稳定 |
| 堆排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) |
不稳定 |
| 归并排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(n) |
稳定 |
- 冒泡排序：两层循环，外循环确定起始比较位置，内循环不断移动，与后一位比较判断是否交换
- 选择排序：两层循环，外循环控制选择次数，内循环遍历取得最值
- 插入排序：两层循环，外循环控制选择插入的对象，内循环向前遍历插入位置
- 希尔排序：不断迭代缩小步距的插入排序，通过大步距减少插入排序中向前遍历的次数
- 快速排序：确定序列中的关键值，根据关键值大小划分序列，子序列继续快排
- 归并排序：迭代到两两排序，再逐层合并排序结果
- 桶排序
- 基数排序
- 计数排序