专栏首页GoLang那点事排序-线性排序,如何做到百万级数据秒级排序,时间复杂度O(n)?

排序-线性排序,如何做到百万级数据秒级排序,时间复杂度O(n)?

我们经常接触的冒泡排序,快速排序,归并排序等,这些排序时间复杂度大多是n^2或者N(logN),他们都是基于比较的排序(就是排序过程中数据两两做比较),那你有知道和了解几种线性排序的算法吗?他们的时间复杂度都是O(n),下面的几个问题你会了吗?

问题

  1. 1000万订单数据金额如何O(n)复杂度排序?
  2. 100万考生成绩如何O(n)复杂度秒级排序?
  3. 100个手机号如何从小到达O(n)复杂度排序?

常见的线性排序

桶排序

桶排序,顾名思义就是把要排序的元素放入各个桶中,然后每个桶中的元素再进行排序,这样最后所有桶中的元素按桶的顺序排列,则所有元素有序,我们假设n个元素,m个桶,那么每个桶中放入(n/m=k)个元素,每个桶中元素的排序可以用之前我们分享过的快速排序,则桶排序的时间复杂度是m * k(logk),我们把k用n/m进行等价替换,所以时间复杂度就编程了 n* log(n/m),当m非常接近n时,那么桶排序的时间复杂度就是O(n)了。

1000万订单数据金额排序答疑:我们来看上面1000万订单数据金额排序的问题,假设我们只有10M内存,我们首先遍历一遍文件,得出金额的最大值,假设最大值50000,也就是说1000万订单数据金额最小值是0,最大值是50000,那么我们对0到50000的金额大小划分1000个桶,把0到50的金额第一个桶,50到100的金额放入第二个桶,以此类推,然后对每个桶的数据进行排序,之后写入磁盘文件,命名为bucket050.txt,以此类推,直到所有桶的数据都排序完毕,排序过程中,当某一个桶的数据过大,10M内存放不下时,可以用同样的思想进行拆分为多个桶,用下面的图描述一个这个过程。

桶排序的示例代码:

计数排序

计数排序跟上面的桶排序非常的类似,我们提到上面每个桶放入的元素是(k=n/m),假设这个k=1,那么相当于每个桶的元素就只有一个,试想一下,我们是不是只要遍历原始数据,就相当于排序完成。

分析下100万考生成绩O(n)复杂度秒级排序

100万考生,看着数据量很大,但我们透过现像看本质,这些数据的最大值是多少呢?750,是的,高考成绩最大值750,最小值0,也就是说我我们只需要751个桶,我们声明一个长度为751的数组,代表751个桶,数组的下标就是考生的成绩,然后我们100万数据遍历,数组的值是这个成绩出现的次数,当100万数据遍历完成后,我们遍历我们创建的这个桶,根据数组中的值确定打印数组下标的次数,结果就是这100考生成绩的排序。我们看代码实现。

我们看下边的图,就能理解上面代码的逻辑了

那么为什么要叫做计数排序呢?如果我想知道上图中result结果中值为2元素的下标在什么位置?该怎么获取呢?你有好的想法吗

首先我们对上图中的bucket的数组顺序求和,得到如下

我们从后往前依次遍历数组param中的元素,当遍历到1时,我我们从求和后的bucket数组中获取下标为1的元素2,也就说到现在为止,包含自己在内的小于等于1的元素只有2个,也就是说1是数组result中的第二个元素,这时小于等于1的元素就只剩1个了,当我们遍历完数组param,得到的结果就是排列有序的了。

基数排序

基数排序属于分配时排序,又称桶子法,也用到了桶的概念,将待排序的元素局部进行排序分配至桶中,依次循环,直到排序完成。

上面的问题中有100个11位手机号进行从小到达排序为了方便,我这里举例使用3个手机号,手机号码如下,我们从后往前依次遍历手机号的每一位,手机号由从数字组成,最小0,最大9,我们一个桶,桶的大小是10。

第一次遍历,三个手机号末尾是1,5,2;放入我们的桶中,那么手机号的顺序就变化为

第二次遍历,三个手机号的倒数第二位是7,5,7;放入我们的桶中,手机号顺序变化为

以此类推,如下图比较方方式,每一次比较都会对手机号的排序做一个调整,最终手机号所有位数都比较完成,排序也就完成,但这里有个需要注意的点,看上面我们第二次遍历时,有两个手机号末尾都是7,这是我们需要用到稳定排序,目的为了防止第一次排好序的最后以为发生了错乱,就是保证7后面的最后一位1,5也是有序的。

我们用到代码来实现基数排序的算法

应用场景

我们由三个问题引出了三种线性排序,这三种线性排序都有自己的特定应用场景,并不是说任何时候都能使用这三种线性排序,我们一块总结一下这三种排序的应用场景。

桶排序:是一种外部排序,适用于数据量比较均匀,数据范围不是很大的排序数据。

计数排序:适用于待排序的数据最大值不是很大情况的下,比如最大值是100000,就不可以了,这样浪费空间太严重,然后排序数据都是正整数,如果不是,就要想办法转换成正整数。

基数排序:适用于那种有高低位的数据,且数据的长度都一样,如果不一样,看看是否能够补全长度,再者,数据每一位的大小都不宜太大,因为数据也是放入桶中的,太大会过多浪费空间。

三种排序你都明白了吗?欢迎留言区讨论

本文分享自微信公众号 - GoLang那点事(aweiaichitudou),作者:那小子阿伟

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

原始发表时间:2019-10-27

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 排序-真的了解快速排序了吗,请解答下题

    我们分析上面的示例,其实比较的就是下一个区间起始值是否在上一个区间的范围内,依次比较,直到匹配失败,就把这个已经匹配过的最小值和最大值放入一个新的区间。

    阿伟
  • 排序-归并排序,一种外排序,递归,非递归,磁盘?

    归并排序是一种分治思想的应用,所以也适合处理大数量的排序,因此也是一种外排序算法,磁盘排序算法,应用场景也较多,比如mysql的排序,sharding-jdbc...

    阿伟
  • 微服务-高并发下接口如何做到优雅的限流

    通俗的来讲,一根管子往池塘注水,池塘底部有一个口子往外出水,当注水的速度过快时,池塘的水会溢出,此时,我们的做法换根小管子注水或者把注水管子的口堵住一半,这就是...

    阿伟
  • 排序算法 归纳总结

    一、直接插入排序、冒泡排序和简单选择排序是最基本的排序方法,它们主要用于元素个数n(n<10000)不是很大的情形。

    week
  • JavaScript ,Python, j

      常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括:

    py3study
  • 如何优雅地给扑克牌排序?(一)——排序算法的数学本质

    不知平常各位打牌时候是否遇到过这样的场景:四人打完升级后,面对两幅混乱的扑克牌,走了一人后想打斗地主,现在要把他们分出一副来,于是打算先排序后分离,然后各种花色...

    magic2728
  • 八大排序算法详解_面试+提升

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

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

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

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

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

    shengjk1
  • 10.1 内部排序

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

    C语言入门到精通

扫码关注云+社区

领取腾讯云代金券