1、最基础排序算法
| 时间复杂度 | 稳定性 | |
| 冒泡排序 | O(n^2) | 稳定 |
| 选择排序 | O(n^2) | 不稳定 |
| 插入排序 | O(n^2) | 稳定 |
2、5个中间改良排序算法
| 时间复杂度 | 稳定性 | |
| 归并排序 | O(nlogn) | 稳定 |
| 希尔排序 | 平均O(nlogn)，最坏O(n^2) | 不稳定 |
| 堆排序 | O(nlogn) | 不稳定 |
| 快速排序 | 平均O(nlogn)，最坏O(n^2) | 不稳定 |
| 随机化快排 | O(nlogn) | 不稳定 |
(1)、归并、堆、快排是渐进性的最优排序算法(在大规模的数据下尤为体现)；
(2)、解决快排最坏情况的方案：随机化快排，随机选择主元；(与输入无关，就是随机器的概率问题了)；
(3)、以上都是比较模型的排序算法，最快时间复杂度为：O(nlogn)；
(4)、归并排序用并行算法的话，时间复杂度：O(n/logn)；
3、3个局限性的排序算法
| 时间复杂度 | 稳定性 | |
| 桶排序 | O(n) | 稳定 |
| 计数排序 | O(n) | 稳定 |
| 基数排序 | O(n) | 稳定 |
(1)、这3个排序算法的时间复杂度都为：O(n)，都是稳定性的排序算法；
(2)、都是以空间换时间为代价的算法，处理数据的规模在较小范围内；
(3)、无重复数字出现：建议用桶排；
(4)、有重复数字出现，用计数/基数排序；基数排序是对计数排序的优化，在辅助空间上的优化，基数排序所需辅助空间为：10个该元素空间，计数排序所需辅助空间为：最大数字+1个空间；
4、空间复杂度
O(n)：桶排，计数，基数
O(logn)：归并，快排，递归堆排
O(1)：非递归堆排，希尔
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
