算法|各种排序算法的稳定性和复杂度总结
本文同时发布在我的个人网站，欢迎访问： http://www.lilongdream.com/2014/04/10/83.html
| 算法 | 时间复杂度 | 辅助空间 | ||
| 数据结构均为数组 | 最好 | 平均 | 最坏 | |
| 冒泡排序（稳定） | O(n) | O(n^2) | O(n^2) | O(1) |
| 直接插入（稳定） | O(n) | O(n^2) | O(n^2) | O(1) |
| 简单选择（不稳定） | O(n^2) | O(n^2) | O(n^2) | O(1) |
| 快速排序（不稳定） | O(n log(n)) | O(n log(n)) | O(n^2) | 平均O(log(n))，最坏O(n) |
| 堆排序（不稳定） | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| 归并排序（稳定） | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| 基数排序（稳定） | ||||
| 希尔排序（不稳定） | O(n^1.3) | O(1) | ||
【算法|各种排序算法的稳定性和复杂度总结】1 http://jsdo.it/norahiko/oxIy/fullscreen
2 15 Sorting Algorithms in 6 Minutes
http://www.youtube.com/watch?v=kPRA0W1kECg
3 Visualization of Quick sort 快速排序的可视化
http://www.youtube.com/watch?v=vxENKlcs2Tw
感谢阅读！
参考资料：
http://bigocheatsheet.com/
推荐阅读
- JS中的各种宽高度定义及其应用
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- 中国MES系统软件随工业化成长
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- 排序（归并排序）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解