排序算法思维导图总结
常用的排序算法包括：
- 冒泡排序
- 插入排序
- 合并排序
- 堆排序
- 快速排序
- 计数排序
- 基数排序
- 桶排序
下面按照稳定性、复杂度、适用特点进行总结。
稳定性：具有相同值的元素在输出数组中的相对次序没有改变。当卫星数据随被排序的元素一起移动时，稳定性比较重要。
复杂度：时间复杂度和空间复杂度。
适用特点：算法需要根据具体条件进行选择。
1.排序算法分类，稳定性和时空复杂度[1]：
2.适用特点[1-4]：
|
特点 |
||
| 插入排序 | 直接插入排序 | 数据基本有序时，可以减少数据交换和移动次数，提高效率 |
| 希尔排序 | 简单，适用于小数据量情况 | |
| 交换排序 | 冒泡排序 | 实际使用中效率较低，对数据有序性非常敏感 |
| 快速排序 | 分治，自顶向下。理论上最好的方法，应用广泛; 如果数据量大而且数据全部放在内存中，那么快速排序是首选的排序方法[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] 《系统程序员成长计划》
