排序的时间复杂度（记忆帖）
排序的时间复杂度（记忆帖）
怕记不住
稳定的排序
| 时间复杂度 | 空间复杂度 | |
|---|---|---|
| 冒泡排序 | 平均O(n2),最好O(n) | 1 |
| 插入排序 | 平均O(n2),最好O(n) | 1 |
| 归并排序 | O(nlogn) | O(n) |
| 桶排序 | O(n) | O(k) |
不稳定的排序
| 时间复杂度 | 空间复杂度 | |
|---|---|---|
| 选择排序 | O(n2) | 1 |
| 希尔排序 | O(nlogn) | 1 |
| 堆排序 | O(nlogn) | 1 |
| 快速排序 | 平均O(nlogn), 最差O(n2) | O(logn) |
附：
1、在第一次排序后，一定能把数据中最大或最小元素放在最终位置上的排序算法是 ：冒泡排序、选择排序、堆排序
2、稳定排序与不稳定排序
- 存在多个关键字相同的记录，如果排序后，这些相同的关键字的相对次序保持不变，则该方法是稳定的
- 反之，不稳定
3、就地排序，排序的空间复杂度为1的排序，有：插入排序、冒泡排序、选择排序、堆排序、希尔排序
4、就平均性能而言，快速排序最快
5、如果要求在排序的数组（或者部分排序的数组中），查找一个数字或统计某个数字出现的次数，都可以尝试使用二分查找。
6、实战：要对公司员工的年龄排序。要求O(n)，空间复杂度O(n)。就可以用桶排序实现。
7、100G的数据，只有2G内存，怎么排序？
- 用归并排序。当出现数据没办法一次装入内存的情况时，一般采用外部排序。将100G的数据分解为多个能够一次性装入内存中的小部分。然后分别把每一个小部分排序，最后对每一个小部分进行归并排序。
注：学渣心里苦，不要学楼主，平时不努力，考试二百五，哭 ~