首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

漫画:“排序算法” 大总结

此外还有冒泡排序的变种,鸡尾酒排序:

第三梯队的排序算法有什么共同点呢?它们的平均时间复杂度都是O(n^2)

冒泡排序、选择排序、插入排序之间,究竟有什么样的差别呢?

首先从性能来分析,冒泡排序插入排序的元素比较交换次数取决于原始数组的有序程度

如果原始数组本来已经接近有序,只需要较少的比较交换次数即可完成排序。比如下面这个数组,只有7和8是逆序的:

如果原始数组大部分元素无序,则需要较多的比较交换次数。比如下面这个数组,绝大部分元素都是无序的:

在此基础上,插入排序的性能略高于冒泡排序。为什么这么说呢?因为冒泡排序每两个元素之间的交换是彼此独立的,比如A和B交换,B和C交换,C和D交换:

而插入排序的元素交换是连续的,比如把B赋值给A,把C赋值给B,把D赋值给C,最后把A赋值给D:

显然,归并排序的连续交换方式省去了许多无谓的交换操作。

再来说说选择排序,选择排序和前面两者不太一样,它的元素比较交换次数是固定的,和原始数组的有序程度无关

因此,当原始数组接近有序时,插入排序性能最优;当原始数组大部分元素无序时,选择排序性能最优

下面再说说排序的稳定性:

冒泡排序和插入排序是稳定排序,值相同的元素在排序后仍然保持原本的先后顺序。

选择排序是不稳定排序,值相同的元素在排序后不一定保持原本的先后顺序。

第二梯队的排序算法有什么共同点呢?它们的性能比第三梯队要高一个量级,其中希尔排序的平均时间复杂度最快可以达到O(n^1.3),快速排序、归并排序、堆排序的平均时间复杂度是O(nlogn)

快速排序、归并排序、堆排序之间,究竟有什么样的差别呢?

还是先从性能来分析,虽然快速排序的平均时间复杂度是O(nlogn),但是在极端情况下,最坏时间复杂度是O(n^2)

而归并排序和堆排序的时间复杂度稳定在O(nlogn)。

至于平均时间复杂度,虽然三者同样都是O(nlogn),但是堆排序比前两者的性能略低一些。为什么呢?主要是由于二叉堆的父子节点在内存中并不连续

在访问内存数据时,对于顺序存储的数据,读写效率往往是最高的。根据CPU的空间局部性原理,CPU在每次访问数据的时候,会把内存中相邻的数据也一并存入缓存。这样一来,CPU以后再访问邻近的数据就不需要重新访问内存,而是访问CPU缓存,从而大大提升了程序执行的效率。

下图是有些夸张的示意:

在堆排序的过程中,常常需要父子节点之间进行比较和交换,而父子节点在数组中的位置并不是相邻,而是相差两倍左右:

反观快速排序和归并排序,无论是快速排序中把元素移动到pivot两侧,还是进行归并排序中的merge操作,都是按照数组元素的自然顺序依次进行比较和交换操作。

因此,堆排序的平均性能比快速排序和归并排序略低。

至于排序的稳定性,归并排序是稳定排序,快速排序和堆排序是不稳定排序

此外,快速排序和堆排序是原地排序,不需要开辟额外空间。而归并排序是非原地排序,在merge操作的时候需要借助额外的辅助数组来完成。

第一梯队的排序算法有什么共同点呢?它们的性能比第二梯队又要高出一个量级,都属于线性时间复杂度的排序算法。

虽然计数排序、桶排序、基数排序同为线性排序算法,但它们的时间复杂度有着很大不同:

计数排序的时间复杂度是O(n+m),其中m是原始数组的整数范围。

桶排序的时间复杂度是O(n),这是在分桶数量是n的前提下。

基数排序的时间复杂度是O(k(n+m)),其中k是元素的最大位数,m是每一位的取值范围。

至于排序的稳定性,这三种排序算法都属于稳定排序

有哪些又出门又奇葩的排序算法呢?

睡眠排序

猴子排序

珠排序

这三种排序算法体现出了发明者天马行空的想象力,大家可以拿来娱乐一下,但是在现实工作中如有排序需求,可千万不要调用它们啊!

—————END—————

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20191226A07GWF00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券