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

此外还有冒泡排序的变种，鸡尾酒排序：

第三梯队的排序算法有什么共同点呢？它们的平均时间复杂度都是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—————