Cheat Sheet
| Class | Algorithm | Average-case | Best-case | Worst-case | Space Complexity | Stable | remark |
|---|---|---|---|---|---|---|---|
| 交换排序 | Bubble | O(n^2) | O(n) | O(n^2) | O(1) | o | |
| Quick | O(nlogn) | O(nlogn) | O(n^2) | O(logn) best, O(n) avg | x | https://zhuanlan.zhihu.com/p/41446726 | |
| Dual Pivot Quick | O(nlogn) | O(nlogn) | O(n^2) | O(logn) best, O(n) avg | x | 比Quick更难达到Worst | |
| 插入排序 | Insertion | O(n^2) | O(n) | O(n^2) | O(1) | o | |
| Binary Insertion | O(n^2) | O(logn) | O(n^2) | O(1) | o | 数组长度小于32王道 | |
| Shell | O(n^1.3) | O(n) | O(n^2) | O(1) | x | https://zhuanlan.zhihu.com/p/87781731 | |
| 选择排序 | Selection | O(n^2) | O(n^2) | O(n^2) | O(1) | x | https://zhuanlan.zhihu.com/p/87190762 |
| Heap | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | x | ||
| 归并排序 | Merge | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | o | https://zhuanlan.zhihu.com/p/88172253 |
| Tim | O(nlogn) | O(nlogn) | O(nlogn) | O(1) best, O(n/2) worst | o | 优化了空间复杂度 | |
| 非比较排序 | Counting | O(k+n) | O(k+n) | O(k+n) | O(k+n) | o | byte[], short[], char[] |
应用场景
小集合：插入排序
大集合、稳定：归并排序
大集合、不稳定：三路快速排序
参考文献
若有收获，就点个赞吧
0 人点赞
