转【算法之常用排序算法(二)】常用排序算法性能比较,及常见面试题

时间:2022-06-19 20:07:16

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

 

排序法

平均时间

最坏情况

最好情况

稳定度

额外空间

备注

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