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

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