各种排序方法的性能比较：
排序法 |
平均时间 |
最坏情况 |
最好情况 |
稳定度 |
额外空间 |
备注 |
1．直接插入 |
O(n2) |
O(n2) |
O(n) |
稳定 |
O(1) |
大部分已排序时较好（简单） |
1．希尔 |
O(nlogn) |
O(nlogn) |
与步长相关 |
不稳定 |
O(1) |
n小时较好（较复杂） |
2．冒泡 |
O(n2) |
O(n2) |
O(n) |
稳定 |
O(1) |
n小时较好（简单） |
2．快排 |
O(nlogn) |
O(n2) |
O(nlogn) |
不稳定 |
O(logn) |
n大时较好,基本有序时反而不好（较复杂） |
3．直接选择 |
O(n2) |
O(n2) |
O(n2) |
不稳定 |
O(1) |
n小时较好（简单） |
3．堆排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
不稳定 |
O(1) |
n大时较好（较复杂） |
4．归并 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
稳定 |
O(n) |
n大时较好（较复杂） |
基数 |
O(d(n+r)) |
O(d(n+r)) |
O(d(n+r)) |
稳定 |
O(r) |
d为位数，r为基数（较复杂） |
计数 |
O(n+k) |
O(n+k) |
O(n+k) |
稳定 |
O(n+k) |
优于比较排序法,0~k为数值范围 |
桶排序 |
O(n+c) |
O (nlogn):所有的元素落到一个桶中 |
O(n) |
稳定 |
O(n+m) |
n为数的个数，m为桶数 c = n*(logn-logm) 桶越多，效率越高，n=m,达到O(n)，但是占用很大的空间，桶内可用快排等 |
（一）基于比较的排序算法：
1、第一类——插入排序法：直接插入排序，希尔。以及不常见的Tree sort、Library sort、Patience sorting 。
2、第二类——交换排序法：冒泡、快排（由冒泡改进而来）。以及不常见的鸡尾酒排序、奇偶排序、梳排序、Gnome sort 。
3、第三类——选择排序法：直接选择、堆排序。
4、第四类——归并排序法：归并排序。以及不常见的Strand sort。
（二）非基于比较的排序算法：
上表中蓝色粗体标识：基数、计数、桶排序。
性能分析及选择排序方法的考量：
O(n^2)的分析：
在数据规模较小时(9W之内)，直接插入（略微好于简单选择）、简单选择差不多。当数据较大时，冒泡排序算法的时间代价是最昂贵的。 另外，普通排序算法基本上都是相邻元素进行比较，因此O(N^2)的排序基本都是稳定的。
O(nlogn)的分析：
其中快速排序无疑是最优秀的。其次是归并排序和希尔排序，堆排序稍微差一些。
先进算法分析：
(1) 就时间性能而言，希尔排序、快速排序堆排序和归并排序都是较为先进的排序方法。耗时远小于O(N^2)级别的算法。
(2) 先进算法之中，快排的效率是最高的。但其缺点十分明显：在待排序列基本有序的情况下，会蜕化成起泡排序，时间复杂度 接近 O(N^2)。
(3) 希尔排序的性能让人有点意外，这种增量插入排序的高效性完全说明了：在基本有序序列中，直接插入排序绝对能达到令人 吃惊的效率。但是希尔排序对增量的选择标准依然没有较为满意的答案，要知道增量的选取直接影响排序的效率。
(4) 归并排序的效率非常不错，在数据规模较大的情况下，它比希尔排序和堆排序都要好。
(5)堆排序在数据规模较小的情况下还是表现不错的，但是随着规模的增大，时间代价也开始和shell和归并两种排序拉开距离。
(6) 多数先进排序都因为跳跃式的比较，降低了比较次数，但是也牺牲了排序的稳定性。
总的来说，并不存在“最佳”的排序算法。必须针对待排序列自身的特点来选择“良好”的算法。
不同条件下，排序方法的选择
1.插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。
反而在这种情况下，快速排序反而慢了。
2.当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。
3.若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。
4.当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
5.当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下,宜用归并排序。
6.当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。
下面有一些指导性的意见：
(1) 数据规模很小，而且待排序列基本有序的情况下，选择直接插入排序或冒泡排序绝对是上策。不要小看它O(N^2)级别。
(2) 数据规模不是很大，完全可以使用内存空间。而且待排序列杂乱无序(越乱越开心)，快速排序永远是不错的选择，当然付出log(N)的额外空间（为栈所需的辅助空间）是值得的。
(3) 海量级别的数据，必须按块存放在外存(磁盘)中。此时的归并排序是一个比较优秀的算法，在数据规模较大的情况下，它比希尔排序和堆排序都要好。
常考问题：
1.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
2.直接插入排序在某一趟结束后未必能选出一个元素放在其最终位置；但是堆排序、冒泡（在首趟即可确定最大值和最小值）、快排可以。
3.已知数组中的每个元素距离最终位置不远，采用直接插入排序最节省时间。
4.直接选择排序关键字比较次数和记录的初始排列顺序无关，都为n(n-1)/2。
5.对n个元素执行快排，在进行第一次划分时，关键字的比较次数总是n-1。
来源：http://blog.csdn.net/cangchen/article/details/44962973