各种排序算法的稳定性和复杂度总结

算法 时间复杂度 辅助空间
数据结构均为数组 最好 平均 最坏
冒泡排序(稳定) 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)

这里有3个很酷的排序算法演示:

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/