0%

“排序算法”小结

说明

本文转载自微信公众号 程序员小灰,系其原创文章,转载已征得作者本人同意,少许改动未涉及核心内容😀

CSDN地址:https://blog.csdn.net/bjweimengshu/article/details/103573147

三个梯队

第三梯队

冒泡排序

漫画:什么是冒泡排序?

选择排序

漫画:什么是选择排序?

插入排序

漫画:什么是插入排序?

鸡尾酒排序

冒泡排序的变种

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

共同点

平均时间复杂度都是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是每一位的取值范围。

其他

睡眠排序

猴子排序

珠排序

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

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

总结

-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道