时间复杂度 | 额外空间复杂度 | 稳定性 | |
---|---|---|---|
选择排序 | O(N^2) | O(1) | 无 |
冒泡排序 | O(N^2) | O(1) | 有 |
插入排序 | O(N^2) | O(1) | 有 |
归并排序 | O(N*logN) | O(N) | 有 |
随机快排 | O(N*logN) | O(logN) | 无 |
堆排序 | O(N*logN) | O(1) | 无 |
计数排序 | O(N) | O(M) | 有 |
基数排序 | O(N) | O(N) | 有 |
- 不基于比较的排序,对样本数据有严格要求,不易改写;
- 基于比较的排序,只要规定好两个样本怎么比大小就可以直接复用;
- 基于比较的排序,时间复杂度的极限是 O(N*logN);
- 时间复杂度 O(N*logN)、额外空间复杂度低于 O(N)、且稳定的基于比较的 排序是不存在的;
- 为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并;
常见的坑
- 归并排序的额外空间复杂度可以变成 O(1),"归并排序" 内部缓存法,但是将变得不再稳定。
- "原地归并排序",会让时间复杂度变成 O(N^2);