| 实现思路 | 时间复杂度 | 空间复杂度 | 特殊情况下 |
|---|---|---|---|
| 选择排序 | O(n^2) | O(1) | O(n^2) |
| 插入排序 | O(n^2) | O(1) | 数组完全有序时为O(n) |
| 冒泡排序 | O(n^2) | O(1) | 数组完全有序时为O(n) |
| 归并排序 | O(n^logn) | O(n) | 数组完全有序时为O(n) |
| 快速排序 | O(n^logn) | O(1) | 数组相同元素较多时O(n) |
| 堆排序 | O(n ^logn) | O(1) | |
| 希尔排序 | O(n^logn) ~ O(n^2) | O(1) |
1.排序的主要问题：
SelectK, topK 问题，逆序对
当数据以流的方式输入时，首先采用优先队列解决
2.排序算法的优化思想：
3.算法的稳定性：
算法的稳定性是指排序前后两个数之间的相对位置关系，并且算法稳定性依赖具体实现
- 不稳定算法：
选择排序 / 插入排序 / 希尔排序 / 堆排序
- 不稳定算法：
归并算法 / 快速排序
若有收获，就点个赞吧
0 人点赞
