概述
最近刚学完 常用排序算法，做个简单总结。
对比表格如下：
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 简单选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 稳定 |
| 直接插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 希尔排序 | O(nlogn)~O(n2) | O(n1.3) | O(n2) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n2) | O(logn)~O(n ) | 不稳定 |
其中前三种 为 简单算法， 后四种为改进算法。
其中，“希尔排序” 改进 “直接插入排序”，因为增大了比较和跳跃的间隔，效果更好。
“堆排” 相当于 “简单选择排序”的升级，通过构造 大（小）顶堆，选出 最大（小）放于堆顶，然后交换，轮询一遍完成排序。
“归并排序” 通过将原数组，按等量的数组块，块内排序后，再让有序数组块两两合并排序，最终合成一个有序数组，达到排序的目的。
“快速排序” 通过寻找 中间分割点，并对分割点两侧的区间（一个全部小于等于 中间分割点，一个全部大于中间分割点），并不断的递归调用，通过交换达到排序的目的。
从上表可看出，每种算法都有自己的优点和缺点，所以都有存在的必要。
简单说来，数据量 较小时，适合用简单算法，复杂算法在构造小数据量的结构时，花费的时间将得不偿失。
另外，从稳定性来看，不同的场景适合选择不同的算法 。 （如同 奥运赛场上，选择 发挥稳定的运动员参赛，还是 发挥不稳定，但却可能创造奇迹的运动员一样）。
辅助空间考虑，如果 内存受限，当然只能 放弃时间性能，选择辅助空间小些的算法。
如有错误，欢迎批评指正，共同提高，谢谢！
最后
以上就是端庄早晨为你收集整理的常用排序算法 的分析与对比的全部内容，希望文章能够帮你解决常用排序算法 的分析与对比所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复