专栏首页信安本原算法之排序(下)

算法之排序(下)

前面两篇文章说了时间复杂度为O(n2)的冒泡排序、插入排序和选择排序;也说了时间复杂度为O(nlogn)的归并排序和快速排序;这次来说一下时间复杂度为O(n)的桶排序、计数排序和基数排序,由于它们的时间复杂度是线性的,所以它们也叫做线性排序(Linear sort),之所以能够做到线性复杂度,是因为它们在排序的时候,不涉及元素之间的比较,同时它们的使用条件也是非常苛刻的。

桶排序(Bucket sort)

桶排序,顾名思义,用桶来对数据进行分割,桶排序是将要排序的数组分到几个有序的桶里面,然后对每个桶里面的数据进行排序,最后将所有数据依次取出,就完成了排序。

来看一下它的时间复杂度,假如将n个数据平均分到m个桶中,每一个桶中有x=n/m个数据,每个桶使用快速排序,时间复杂度为O(xlogx),m个桶的时间复杂度就是O(m*xlogx),因为x=n/m,所以时间复杂度为O(nlog(n/m)),当桶的个数接近数据n时, log(n/m) 将会是一个非常小的数,时间复杂度就接近与O(n)了。

但是,上面用了假如两个字,因为要使用桶排序所需要的前提条件比较多,首先数据需要很容易就可以划分到m个桶中,而且每一个桶它本身就需要有先后顺序,这样桶就不需要再进行排序了。其次,我们上面把均匀两个字给加粗了,只有在桶中的数据比较平均时才可以,如果每一个桶中的数据差距是非常大的,那桶内排序的时间复杂度就不是常量级了,最极端的情况就是分到了一个桶中,那时间复杂度就变成了O(nlogn)了。

桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中,数据量比较大,内存有限,无法将数据全部加载到内存中。

假如有10个G的订单数据,订单金额都是正整数,要根据金额大小进行排序,而内存又比较小,无法同时装下所有的数据该怎么办?

用桶排序的思路就是,先扫描一遍订单,看一下大概的金额分布,假如金额都分布在1到1万,我们就可以将金额分到10个桶里,第一个桶是1~1000,依此类推,它们的顺序依次是0,1,2…9。

理想情况下,就是它们均匀分布在每一个桶中,然后我们在每一个桶中使用快速排序,最后将它们依次输出出来。那如果1000-2000的金额比较多的话,还是无法直接放到内存中,那就继续使用桶排序进行分割,直到全部排序完成。


计数排序(Counting sort)

计数排序基本上属于桶排序的特殊情况,在要排序的范围不大的时候,比如有x个数据,那我们就分x个桶,每个桶内的数据都是相同的,这样我们就省下了桶内排序的时间。

至于为什么要叫计数,这个是跟计数排序的实现方法有关的,不过我还没有理解清楚,这里就先放下了,这个坑之后再填。


基数排序(Radix sort)

再来一个排序问题来看,如果有十万个手机号码,要将这十万个手机号从小到大排序。如果使用前面的桶排序和计数排序,它的范围比较大,这两种算法明显都不适合。

现在就可以用到第三个排序方法,基数排序。在刚刚的问题里,我们可以明显的看出来,当一个号码前面的几位已经明显大于另一个号码,那后面的也就不需要比较了,也就是说我们需要将手机号排序为第一个数字从小到大排序,第一个数字相同的,按照第二个数字从小到大排序,第二个数字相同的,按照第三个,依此类推,那如何才能排列成这样呢。

这里我们用一个新的思路来考虑,我们先按照最后一位数字的大小来进行排序,然后再按照倒数第二位进行排序,依此类推,经过11次排序以后,就完成了对整个手机号的排序。这里需要注意一下的是,必须用稳定的排序算法来实现,如果是非稳定的排序算法,之前的排序就没有任何的意义了。

用几个字符串表示的话,就是这个样子的

再举一个订单的例子,对于一批订单,我们希望将它按照金额的大小排序,如果金额相同,就按照下单的时间进行排序,一样是使用这样的方法。

那如果我们需要排序的数据并不是等长的,又该如何去处理,比如说要对单词进行排序,有的单词是五个字母,有的单词是十五个字母,那该如何处理?

我们可以把所有的字母都补到一样的长度,不足的后面补0,因为根据ASCII码我们可以发现,所有的字母都在数字0之后,它并不会影响排序的正常进行,所以依旧可以使用基数排序来进行。

参考文档

极客时间-数据结构与算法之美

本文分享自微信公众号 - 无心的梦呓(wuxinmengyi),作者:Vesel无心

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

原始发表时间:2020-02-06

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法之排序(上)

    排序算法有很多种,甚至有很多都完全没有听过,我们最常见,也最经典的就是:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

    信安本原
  • 算法之排序(中)

    上一篇文章说了时间复杂度为O(n2)的冒泡、插入和选择三个排序方式,它们只适合在数据规模比较小的时候,接下来要说的是两个时间复杂度为O(nlogn)的算法,归并...

    信安本原
  • 算法之排序(中)-c语言实现

    上一篇文章里说了归并排序和快速排序,它们的代码实现是非常相似的,只要理解了其中的具体实现,还是比较容易写出代码的。

    信安本原
  • 桶排序/基数排序(Radix Sort)

    基本思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要...

    瑾诺学长
  • 八大排序算法详解_面试+提升

    八大排序算法详解_面试+提升 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排...

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

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

    小灰
  • 排序算法总括-java版

    内部排序就是仅仅依赖于内存就可以进行的排序,比如有交换排序、插入排序、选择排序、归并排序、基数排序

    shengjk1
  • 八大排序算法图文介绍

    八大排序算法图文介绍 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排...

    Java帮帮
  • 《十大经典排序算法》简介

    十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的...

    搜云库
  • 数据结构与算法系列之常用算法:排序算法

    根据数组的元素个数、nearly sorted(近单调性:单调升序和单调降序)和元素类型等来选在具体排序算法。例如对整数排序:

    尜尜人物

扫码关注云+社区

领取腾讯云代金券