查看原文
其他

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

CSDN云计算 2019-12-26

以下文章来源于程序员小灰 ,作者小灰

戳蓝字“CSDN云计算”关注我们哦!








冒泡排序:

漫画:什么是冒泡排序?


选择排序:

漫画:什么是选择排序?


插入排序:

漫画:什么是插入排序?


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

漫画:什么是鸡尾酒排序?


第三梯队的排序算法有什么共同点呢?它们的平均时间复杂度都是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是每一位的取值范围。


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



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


睡眠排序

猴子排序

珠排序


漫画:三种 “奇葩” 的排序算法


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









福利

扫描添加小编微信,备注“姓名+公司职位”,加入【云计算学习交流群】,和志同道合的朋友们共同打卡学习!



推荐阅读:

真香,朕在看了!

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存