线性排序:

线性排序即排序算法的时间复杂度是线性的,也就是 O(n)。桶排序、计数排序、基数排序这三个算法是不基于比较的排序算法,都不涉及元素之间的比较操作。

桶排序(Bucket sort)

桶排序,顾名思义,会用到「桶」,核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序。桶内排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,我们需要做到这两点:

  • 在额外空间充足的情况下,尽量增大桶的数量

  • 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。

算法步骤

  • 设置固定数量的空桶。

  • 把数据放到对应的桶中。

  • 对每个不为空的桶中数据进行排序。

  • 拼接不为空的桶中数据,得到结果。

算法演示

1940317-ad940e1d1a16fc39.gif

参考:https://www.cxyxiaowu.com/2115.html

如何使用

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

应用:

  • 如何根据年龄给 100 万用户排序

  • 现在你有 10 个接口访问日志文件,每个日志文件大小约 300MB,每个文件里的日志都是按照时间戳从小到大排序的。你希望将这 10 个较小的日志文件,合并为 1 个日志文件,合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有 1GB,你有什么好的解决思路,能“快速”地将这 10 个日志文件合并吗?

  • 有 10GB 的订单数据,我们希望按订单金额(假设金额都是正整数)进行排序,但是我们的内存有限,只有几百 MB,没办法一次性把 10GB 的数据都加载到内存中。

  • 一年的全国高考考生人数为500 万,分数使用标准分,最低100 ,最高900 ,没有小数,要求对这500 万元素的数组进行排序。

  • 在一个文件中有10G个整数,乱序排列,要求找出中位数。内存限制为2G。只写出思路即可(内存限制为2G意思是可以使用2G空间来运行程序,而不考虑本机上其他软件内存占用情况。) 关于中位数:数据排序后,位置在最中间的数值。即将数据分成两部分,一部分大于该数值,一部分小于该数值。中位数的位置:当样本数为奇数时,中位数=(N+1)/2 ; 当样本数为偶数时,中位数为N/2与1+N/2的均值(那么10G个数的中位数,就第5G大的数与第5G+1大的数的均值了)。

参考:

https://sort.hust.cc/9.bucketsort

https://time.geekbang.org/column/article/41913

https://baike.baidu.com/item/桶排序/4973777

https://www.cxyxiaowu.com/2115.html

本文地址: http://chenxm.cc/article/981.html
版权声明: 本文为原创文章,版权归  陈新明  所有,欢迎分享本文,转载请保留出处!
上一篇: 使用scp提示错误ECDSA host key for [ip address] has changed and you have requested strict checking.
下一篇: python 排序算法——线性排序之计数排序(Counting sort)
发表评论

还没有留言,还不快点抢沙发?