常见排序算法总结

总结了常用的排序算法，以及对应分析

相关链接：

1. 冒泡排序 (opens new window)
2. 选择排序 (opens new window)
3. 插入排序 (opens new window)
4. 快速排序 (opens new window)
5. 归并排序 (opens new window)
6. 希尔排序 (opens new window)
7. 桶排序 (opens new window)
8. 基数排序 (opens new window)
9. 堆排序 (opens new window)

总结各种排序算法的时间复杂度和空间复杂度，以及其对应的稳定性

算法种类	最好情况	平均时间复杂度	最坏情况	空间复杂度	是否稳定
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	是
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	是
插入排序	O(n)	O(n^2)	O(n^2)	O(1)	是
快速排序	O(nlogn)	O(nlogn)	O(n^2)	O(logn)	否
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	是
希尔排序		O(n1.3)-O(n2)		O(1)	否
桶排序	O(n)	O(n*(log(n/m)+1))	O(n^2)	O(n+m)	是
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	是
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	否