排序算法性能对比
|
129 浏览
![]()
排序算法性能对比
| 排序方法 |
最好时间 |
平均时间 |
最坏时间 |
辅助存储 |
稳定性 |
备注 |
| 简单选择排序 |
O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
不稳定 |
n小时较好 |
| 直接插入排序 |
O(n) |
O(n^2) |
O(n^2) |
O(1) |
稳定 |
大部分已有序时较好 |
| 冒泡排序 |
O(n) |
O(n^2) |
O(n^2) |
O(1) |
稳定 |
n小时较好 |
| 希尔排序 |
O(n) |
O(nlogn) |
O(ns)1<s<2 |
O(1) |
不稳定 |
s是所选分组 |
| 快速排序 |
O(nlogn) |
O(nlogn) |
O(n^2) |
O(logn) |
不稳定 |
n大时较好 |
| 堆排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) |
不稳定 |
n大时较好 |
| 归并排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(n) |
稳定 |
n大时较好 |
结论
- 简单的说,所有相等的数经过某种排序方法之后,仍能保持他们在排序之前的相对次序,就称为这种排序方法是稳定的,反之,就是非稳定的,例如:一组数排序前是a1,a2,a3,a4,a5,其中a2=a4,经过某种排序后a1,a2,a4,a3,a5,则说这种排序是稳定的,因为a2排序在a4的前面,排序后它还是在a4的前面.
假如变成a1,a4,a2,a3,a5就不是稳定的了.各种 算法中的稳定的排序算法有直接插入排序,冒泡排序,归并排序.而不稳定的排序算法有希尔排序,快速排序,简单选择排序,堆排序
- 时间复杂度为O(n^2)的排序算法有直接插入排序,冒泡排序,快速排序,简单选择排序: 时间复杂性为O(nlogn)的排序算法有堆排序,归并排序
- 空间复杂度为O(1)的算法有简单选择排序,直接插入排序,冒泡排序,希尔排序,堆排序: 空间复杂度为O(n)的算法是归并排序;空间复杂度为O(logn)的算法是快速排序
- 虽然直接插入排序和冒泡排序的速度比较慢,但是当初始序列整体或局部有序时,这两种排序算法会有较好的效率.当初始序列整体或局部有序时,快速排序算法的效率会下降.当排序序列较小且不要求稳定性时,直接选者排序效率较好;要求稳定性时,冒泡排序效率较好
- 除了以上这几种排序算法以外,还有位图排序,桶排序,基数排序等,每种排序算法都有其最佳适合的场景,例如,当待排序数据规模巨大,而对内存大小又没有限制时,位图排序则是最高效的排序算法
