转载请注明出处：http://blog.csdn.net/ns_code/article/details/20540069
这篇博文我们简要地总结下各种内部排序方法。
这10种排序算法中，前面7种属于建立在“比较”基础上的排序算法，通过决策树已经证明，任何基于比较进行的排序算法的时 间复杂度不可能再优于O(n*logn)。后面3种不是建立在比较的基础上的，因此，可以达到线性运行时间。
下面我们给出各种排序方法的时空复杂度的表格（属于自己总结，有不对的地方，希望大家指正或补充）。
排序方法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 是否稳定 |
冒泡排序 | O(n*n) | O(n*n) | O(1) | 稳定 |
插入排序 | O(n*n) | O(n*n) | O(1) | 稳定 |
简单选择排序 | O(n*n) | O(n*n) | O(1) | 不稳定 |
希尔排序 | 不定 | O(n^4/3) | O(1) | 不稳定 |
堆排序 | O(n*logn) | O(n*logn) | O(1) | 不稳定 |
归并排序 | O(n*logn) | O(n*logn) | O(n) | 稳定 |
快速排序 | O(n*logn) | O(n*n) | O(n*logn) | 不稳定 |
计数排序 | O(n+k) | O(n+k) | O(k) | 稳定 |
基数排序 | O(d(n+k)) | O(d(n+k)) | O(k) | 稳定 |
桶排序 | O(n) | O(n) | 不定 | 取决于桶内排序 |
源码包括：冒泡排序、选择排序、插入排序、希尔排序、堆排序、归并排序、快速排序、计数排序、基数排序等，没有实现桶排序。
完整源码打包下载地址：http://download.csdn.net/detail/mmc_maodun/6995321
内部排序总结（附各种排序算法源码）,布布扣,bubuko.com
原文：http://blog.csdn.net/ns_code/article/details/20540069