排序算法——十大排序算法总结与对比

  • Post author:
  • Post category:其他


一、十大排序算法复杂度对比

二、关于排序算法的总结

1、基数排序仅仅适用于整型数的排序,一般不与另外的排序方法一起比较。

2、关于算法的稳定性:不稳定的算法有 “快希选堆”——快速排序,希尔排序,选择排序和堆排序。

3、关于问题的规模

(1)数据规模较大时,应该选择平均复杂度较好的算法:优先考虑排序、归并排序、堆排序树形选择排序、希尔排序等。

(2)数据规模较小时选择较简单的算法:插入排序、交换排序、直接选择排序等。

4、序列的初始状态

(1)初始记录接近有序时:选用直接插入、堆排序、冒泡排序、归并排序、希尔排序等,其中最快的是冒泡排序和插入排序。此时只有记录操作,没有记录移动。平均时间复杂度为Ο(n)。

(2)初始记录无序时最好选择快速排序、希尔排序、简单选择排序。它们通过“振荡”的方式让数值相差不大但是位置相差很大的元素快速到位。

5、时间和辅助空间

当空间复杂度高且排序规模较大时,排序需要的内存空间可能会超出限制,需要频繁地从外部存储设备中读写数据,这是算法的性能会急剧下降,所以应该避免使用一些空间复杂度高的算法,比如希尔排序和树形选择排序。

6、关于记录的大小

如果记录占用的空间比较大,排序时应该选择移动次数少的算法,比如:直接选择排序和直接插入排序。

7、堆排序对空间的要求低于排序,并且不会出现快速排序最差的情况(快速排序遇到逆序时,退化为冒泡排序)。



版权声明:本文为daimadog原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。