<aside> 💡 **排序的稳定性：**待排序数组中相等的数经过排序算法后依然保持它们在排序前的相对次序。
</aside>
| 排序算法 | 平均时间 | 最优时间 | 最坏时间 | 额外空间 | 稳定性 | 结构 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(1) | 稳定 | 无序，有序 | ||
| 选择排序 | O(n^2) | O(1) | 不稳定 | 有序，无序 | ||
| 插入排序 | O(n^2) | O(n) | O(1) | 稳定 | 有序，无序 | |
| 希尔排序 | O(n^(1.3～2)) | O(1) | 不稳定 | |||
| 快速排序 | O(nlogn) | o(n^2) | O(logn)~O(n) | 不稳定 | ||
| 归并排序 | O(nlogn) | O(n) | 稳定 | |||
| 堆排序 | O(nlogn) | O(1) | 不稳定 | 最大堆，有序 | ||
| 计数排序 | O(n+max) | O(max） | 稳定 | |||
| 桶排序 | O(n+nlogn-nlogm) | O(n) | O(m) | 稳定 | ||
| 基数排序 | O(d*(n+m)) | O(m) | 稳定 |
参考链接
https://mp.weixin.qq.com/s?__biz=MzUwOTA4MDM2OQ==&mid=2247490722&idx=1&sn=def1a6f829d83b25e328748b2ee9577a&chksm=f916fafcce6173ead188a3e7ab8d5257cd652754f4d542547450923f59be7a48aa1d7c91e64a&scene=27