Skip to content

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较大时,关键字元素可能出现本身是有序的,对稳定性没有要求时宜用堆排序
  • 快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
  • 堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。