转【算法之常用排序算法（二）】常用排序算法性能比较，及常见面试题

各种排序方法的性能比较：

（一）基于比较的排序算法：

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