专栏首页程序员小灰漫画:“排序算法” 大总结

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

冒泡排序:

漫画:什么是冒泡排序?

选择排序:

漫画:什么是选择排序?

插入排序:

漫画:什么是插入排序?

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

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

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

本文分享自微信公众号 - 程序员小灰(chengxuyuanxiaohui),作者:小灰

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:什么是希尔排序?

    插入排序顾名思义,就是在排序的过程中,把数组的每一个元素按照大小关系,插入到前面有序区的对应位置。

    小灰
  • Windows XP源码泄露

    4chan 论坛的一名用户发帖称 Windows XP 源码已被泄露,并在帖子里面附上了一张正在解压 Windows NT 内核源码的截图,从解压路径来看,被泄...

    小灰
  • 著名的三门问题,是在 “胡扯” 吗?

    上周,小灰写了一篇关于“三门问题”的漫画,引起了小伙伴们的激烈争论。没看过的小伙伴可以看一看:

    小灰
  • 常见排序算法分类

      此篇博客不讨论排序算法的思想,时间复杂度,空间复杂度,实现代码。只介绍常见排序算法有哪些,并按照什么进行分类。   排序算法分为两大类: 比较类...

    Dabelv
  • Java常用排序算法/程序员必须掌握的8大排序算法

    Java常用排序算法/程序员必须掌握的8大排序算法 分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排...

    zhisheng
  • 十大经典排序算法的 JavaScript 实现

    https://segmentfault.com/a/1190000009332932

    前端博客 : alili.tech
  • EXcel如何排序,高手不告诉你的5个小技巧

    很多人在办公中都会接触到EXccel,也会用到里面的EXcel排序功能,一说到EXcel排序,很多小伙伴都觉得这个功能很简单啊,已经掌握了,没什么好学习的,其实...

    高效办公
  • 十大经典排序算法 -- 动图讲解

    外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

    互扯程序
  • 排序算法(1)---基本概念

    排序与我们日常生活中息息相关,比如,我们要从电话簿中找到某个联系人首先会按照姓氏排序、买火车票会按照出发时间、买东西会按照销量排序、查找文件会按照最近修改时间排...

    逆月翎
  • 10.1 内部排序

    1、排序(Sorting)时计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。

    闫小林

扫码关注云+社区

领取腾讯云代金券