对冒泡、快排、堆排这3个算法做了验证,结果分析如下:

排序算法C语言实现——冒泡、快排、堆排对比-LMLPHP

一、结果分析

时间消耗:快排 < 堆排 < 冒泡。

空间消耗:冒泡O(1) = 堆排O(1) < 快排O(logn)~O(n) 。

应用推荐:

  1、速度最快、且允许占用少量的空间:选快排。

  2、速度快且空间最小(O(1)):选堆排。

  3、要求相同大小的元素顺序不能变更:选冒泡。

  4、完全不考虑空间消耗的:用基排(极限情况下时间O(n),限制较多,不单独说了)。

冒泡排序:

  优点:稳定、空间复杂度O(1)

  缺点:慢

  时间复杂度最好为n(传入的数组有序,一轮循环即可截止),最坏为n^2,平均为n^2。呈现为n增大10倍,耗时增加100倍。

  在对稳定性有要求的场景下,即相同大小的元素先后顺序不能变更,冒泡排序表现较佳。快排和堆排都是不稳定的。冒泡每次比较相邻的元素,只有不等时才考虑是否交换,所以冒泡不会改变相同大小的元素的顺序,是稳定的排序算法。

快速排序:

  优点:快

  缺点:不稳定、空间复杂度O(logn)~O(n)

  时间复杂度最好为nlogn,最坏为n^2(每次key都在首或尾,栈深度达到n),平均为nlogn。

  为了减小最坏情况发生的概率,我们在选择Key的时候,取了首、尾和中间这3个元素里的中间大小的元素作为Key

  相比其他两种算法,快排需要依靠函数栈(递归)或其他类型的存储空间(非递归)来存储每次划分的区间。最好的情况下,每次都平均划分,需要额外的logn的空间;最坏情况下每次都划分在首或尾,则额外的空间花销达到n。

堆排序:

  优点:快(比较快排慢点)、空间复杂度O(1)

  缺点:不稳定

  时间复杂度稳定在nlogn。

  快排和堆排的时间复杂度都是nlogn,为什么快排会更快呢?因为堆排的复杂度的常系数更大。我们从另一个角度来看。堆排每次将堆顶元素取出,取而代之的是堆底元素。而这个新的堆顶元素显然是比较小的,肯定要比其中一个子节点小。于是调整堆时,拿刚换上来的较小的根与下面的子节点比较,结果有很大可能是要交换多次(甚至于被换回堆底)。这种比较是概率不均等的、很不划算的。而堆排中充斥着大量这种不均等的比较,造成很多多余的交换,这就是为什么堆排会更慢。

二、源码

冒泡:https://www.cnblogs.com/JoZSM/p/9768735.html

快排:https://www.cnblogs.com/JoZSM/p/9768781.html

堆排:https://www.cnblogs.com/JoZSM/p/9783872.html

验证代码:涉及到造数据、存文件等,代码较长,不贴出来了。有需要的可以留言。

05-01 02:11