欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

快速排序 Vs. 归并排序 Vs. 堆排序——谁才是最强的排序算法

程序员文章站 2022-05-09 11:46:24
知乎上有一个问题是这样的: 堆排序是渐进最优的比较排序算法,达到了O(nlgn)这一下界,而快排有一定的可能性会产生最坏划分,时间复杂度可能为O(n^2),那为什么快排在实际使用中通常优于堆排序? 昨天刚好写了一篇关于快排优化的文章,今天再多做一个比较吧。首先先看一个排序算法图: 排序方法| 平均情 ......

知乎上有一个问题是这样的:

堆排序是渐进最优的比较排序算法,达到了o(nlgn)这一下界,而快排有一定的可能性会产生最坏划分,时间复杂度可能为o(n^2),那为什么快排在实际使用中通常优于堆排序?

昨天刚好写了一篇关于快排优化的文章,今天再多做一个比较吧。首先先看一个排序算法图:

排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 o(n^2) o(n) o(n^2) o(1) 稳定
简单选择排序 o(n^2) o(n^2) o(n^2) o(1) 稳定
直接插入排序 o(n^2) o(n) o(n^2) o(1) 稳定
希尔排序 o(nlogn)~o(n^2) o(n^1.3) o(n^2) o(1) 不稳定
堆排序 o(nlogn) o(nlogn) o(nlogn) o(1) 不稳定
归并排序 o(nlogn) o(nlogn) o(nlogn) o(n) 稳定
快速排序 o(nlogn) o(nlogn) o(n^2) o(logn)~o(n) 不稳定

可以看到,到达nlogn级别的排序算法,一共有三种,分别是堆排序,归并排序以及快速排序,其中只有归并排序最稳定。那么,为什么要说快速排序的平均情况是最快的呢?

实际上在算法分析中,大o的作用是给出一个规模的下界,而不是增长数量的下界。因此,算法复杂度一样只是说明随着数据量的增加,算法时间代价增长的趋势相同,并不是执行的时间就一样,这里面有很多常量参数的差别,比如在公式里各个排序算法的前面都省略了一个c,这个c对于堆排序来说是100,可能对于快速排序来说就是10,但因为是常数级所以不影响大o。

另外,即使是同样的算法,不同的人写的代码,不同的应用场景下执行时间也可能差别很大。下面是一个测试数据:

测试的平均排序时间:数据是随机整数,时间单位是s
数据规模    快速排序       归并排序        希尔排序        堆排序
1000万       0.75           1.22          1.77          3.57
5000万       3.78           6.29          9.48         26.54  
1亿          7.65          13.06         18.79         61.31

堆排序每次取一个最大值和堆底部的数据交换,重新筛选堆,把堆顶的x调整到位,有很大可能是依旧调整到堆的底部(堆的底部x显然是比较小的数,才会在底部),然后再次和堆顶最大值交换,再调整下来,可以说堆排序做了许多无用功。

总结起来就是,快排的最坏时间虽然复杂度高,但是在统计意义上,这种数据出现的概率极小,而堆排序过程里的交换跟快排过程里的交换虽然都是常量时间,但是常量时间差很多。