排序算法思维导图总结

Published: 25 Sep 2011 Category:

常用的排序算法包括:

  1. 冒泡排序
  2. 插入排序
  3. 合并排序
  4. 堆排序
  5. 快速排序
  6. 计数排序
  7. 基数排序
  8. 桶排序

下面按照稳定性、复杂度、适用特点进行总结。

稳定性:具有相同值的元素在输出数组中的相对次序没有改变。当卫星数据随被排序的元素一起移动时,稳定性比较重要。

复杂度:时间复杂度和空间复杂度。

适用特点:算法需要根据具体条件进行选择。

1.排序算法分类,稳定性和时空复杂度[1]:

2.适用特点[1-4]:

   

特点

插入排序 直接插入排序 数据基本有序时,可以减少数据交换和移动次数,提高效率
希尔排序 简单,适用于小数据量情况
交换排序 冒泡排序 实际使用中效率较低,对数据有序性非常敏感
快速排序 分治,自顶向下。理论上最好的方法,应用广泛; 如果数据量大而且数据全部放在内存中,那么快速排序是首选的排序方法[4]
选择排序 简单选择排序 对有序性不敏感,交换次数少
堆排序 不需要递归,适合大数据量,可用来实现优先队列
其他排序 合并排序 分治,自底向上。对有序性不敏感,需要辅助空间,不适合大数据量;在处理大量数据的排序时,它不要求被排序的数据全部在内存中,所以在数据大于内存的容纳能力时,合并排序能大显身手。合并排序最常用的地方是数据库管理系统(DBMS)[4]
非基于比较 计数排序 数据范围需要不大
基数排序 关键字需要可分解
桶排序 数据分布均匀
在数据量不大时,所有排序算法性能差别不大。有文章指出,高级排序算法在元素个数多于1000 时,性能才出现显著提升。在90%的情况下,我们存储的元素个数只有几十到上百个而已,比如进程数、窗口个数和配置信息等等的数量都不会很大,冒泡排序其实是更好的选择。[4]

3.算法选择[3]

最后推荐一个网站Sorting Algorithm Animations,这里可以看到各种排序算法在不同数据条件下排序过程的动画演示,非常直观。

参考文献

[1]算法之排序算法,董的博客,http://dongxicheng.org/structure/sort/

[2]八种排序算法总结,http://blog.csdn.net/yfqvip/article/details/3344007

[3] 基本排序算法比较与选择,http://blog.csdn.net/ctang/article/details/37914

[4] 《系统程序员成长计划》