孟习笔谈
7各种排序算法的比较
发布时间:
1 排序算法复杂度表
| 排序算法 | 最佳时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 稳定性 | 空间复杂度 |
| 冒泡排序 | O(N) | O(N^2) | O(N^2) | 稳定 | O(1) |
| 插入排序 | O(N) | O(N^2) | O(N^2) | 稳定 | O(1) |
| 归并排序 | O(NlogN) | O(NlogN) | O(NlogN) | 稳定 | O(N) |
| 选择排序 | O(N^2) | O(N^2) | O(N^2) | 不稳定 | O(1) |
| 希尔排序 | O(N) | O(N^(3/2)) | O(N^S)（1<S<2） | 不稳定 | O(1) |
| 快速排序 | O(NlogN) | O(NlogN) | O(N^2) （1<S<2） | 不稳定 | O(logN) |
| 堆排序 | O(NlogN) | O(NlogN) | O(NlogN) | 不稳定 | O(1) |
注：logN表示以2为底N的对数。
1.稳定性比较
插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的。选择排序、希尔排序、快速排序、堆排序是不稳定的。
2.时间复杂性比较
插入排序、冒泡排序、选择排序的时间复杂性为O(n2)；快速排序、堆排序、归并排序的时间复杂性为O(nlog2n)；桶排序的时间复杂性为O(n);
若从最好情况考虑，则直接插入排序和冒泡排序的时间复杂度最好，为O(n)，其它算法的最好情况同平均情况相同；若从最坏情况考虑，则快速排序的时间复杂度为O(n2)，直接插入排序和冒泡排序虽然平均情况相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情况对直接选择排序、堆排序和归并排序影响不大。
由此可知，在最好情况下，直接插入排序和冒泡排序最快；在平均情况下，快速排序最快；在最坏情况下，堆排序和归并排序最快。
3.辅助空间的比较
桶排序、二路归并排序的辅助空间为O(n)，快速排序的辅助空间为O(log2n)，最坏情况为O(n)，其它排序的辅助空间为O(1);
4.其它比较
- 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。
- 当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。
- 若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。
- 当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
- 当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序
- 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
- 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。