内部排序算法的比较
- 时间复杂度
|
最坏 |
最好 |
平均 |
注 |
| 直接插入 |
O(n2) |
O(n) |
O(n2) |
折半插入与之类似 |
| 冒泡 |
O(n2) |
O(n) |
O(n2) |
|
| 简单选择 |
|
|
O(n2) |
与初态无关 |
| 希尔 |
|
|
O(n1.3) |
具体不确定 |
| 快排 |
O(n2) |
|
O(nlog2n) |
分治 |
| 归并 |
|
|
O(nlog2n) |
分治 |
| 堆排序 |
|
|
O(nlog2n) |
线性时间建堆 |
| 基数排序 |
|
|
O(d(r+n)) |
与初态无关 |
- 空间复杂度
|
最坏 |
平均 |
注 |
|
| 直接插入 |
|
O(1) |
|
|
| 冒泡 |
|
O(1) |
|
|
| 简单选择 |
|
O(1) |
|
|
| 希尔 |
|
O(1) |
|
|
| 快排 |
O(n) |
O(log2n) |
递归栈 |
|
| 归并 |
|
O(n) |
|
|
| 堆排序 |
|
O(1) |
|
|
| 基数 |
|
O® |
r队列 |
|
3.稳定性
| 稳定性 |
排序 |
| 稳定 |
直接插入，折半插入，冒泡，归并，基数 |
| ---------- |
---------------------------- |
| 不稳定 |
希尔，快速，简单选择，堆排序 |
- 特点
-
冒泡，子序列全局有序
-
简单选择，子序列全局有序
-
快速，每次确定一个元素的最终位置
若选取第一个元素作pivot（枢轴）
当前序列越有序，复杂度越趋于O(n2)
-
堆排序，子序列全局有序
适合关键字较多的情况
例：查找出1000个数中最大的10个
解：使用前10个数建立小根堆，每次从后面剩余中取1个数，与根比较，若大则将 根替换，否则舍弃取下一个数比较。
-
（直接，折半）插入排序，子序列局部有序
-
希尔排序
和堆排序一样，不适合用链式结构，因为是跳着读取，应用了顺序表的随机访问存取性质，若改为链式存储，则会降低算法效率
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
