美文网首页
O(n)的桶排序、计数排序、基数排序

O(n)的桶排序、计数排序、基数排序

作者: isLJli | 来源:发表于2020-06-27 11:42 被阅读0次

    这三种算法不是基于元素之间的比较(桶排序还是有的)

    桶排序:就是分为m个区域,让每个数据都放到自己相应的区域内,然后在每个区域利用快速排序为里面的数值排序,然后把每个区域的数据串起来就是排序好的数据了。他们的空间复杂度是O(n*log(n/m)),但是如果你把m个区域分成像总数n那么多,那么基本每个区域就不用排序了,就是o(n)。

    缺点:某些区域内可能存放的数据很多,有些区域可能存放的数据很少,那么就变成了快排了,o(nlogn)。

    场景:适合用于外部存储中,比如要排序的文件有10个G,但是内存只有几百M,我们可以分100个区域甚至更多,先遍历一篇让每个数据找到自己的区域,然后依次把每个区域放在内存中进行快速排序,排序好的文件就可以了。

    计数排序:计数排序这个真的就不用比较元素之间的大小,它是先得到数组中的最大值,然后我就分成那么多区域,注意数据中不能有负数,然后遍历一遍数组,把得到的数值作为区域的下标,然后这个区域的下标+1,然后在遍历一次区域,把在它之前和它自己本身的数值作为它的数据,然后再从尾到头遍历区域,加入到新的数组中。

    image

    基数排序:

    例子:排序10万个手机号

    相关文章

      网友评论

          本文标题:O(n)的桶排序、计数排序、基数排序

          本文链接:https://www.haomeiwen.com/subject/ilmmfktx.html