排序所花费时间不受数据初始排列特性影响算法的是快速排序。
最好情况下时间复杂度为o(n)的算法是直接插入排序法。
总结：
排序方法 平均时间 最好情况 最坏情况 辅助存储 稳定性
选择排序 o(n^2) o(n^2) o(n^2) o(1) 不稳定
插入排序 o(n^2) o（n） o(n^2) o(1) 稳定
冒泡排序 o(n^2) o(n^2) o(n^2) o(1) 稳定
希尔排序 o（n^1.25） -- -- o(1) 不稳定
快速排序 o（nlogn） o（nlogn）o(n^2) o（nlogn) 不稳定
堆排序 o（nlogn） o（nlogn） o（nlogn） o(1) 稳定
归并排序 o（nlogn） o（nlogn） o（nlogn） o（n） 稳定
基数排序 o（d+(n+rd)）o（d+(n+rd)）o（d+(n+rd)）o（rd） 稳定
一些结论：
若待排序的记录数目较小时，可采用插入排序和选择排序；
若待排序记录按关键字基本有序，则宜采用直接插入排序或冒泡排序；
当n很大且关键字的位数较少时，采用链式基数排序较好；
若n较大时，则应采用时间复杂度为o(nlogn)的排序方法——快速排序，堆排序，归并排序
本文转自 寂岚峰 51CTO博客，原文链接：http://blog.51cto.com/13271983/1971865，如需转载请自行联系原作者
