桶类:为什么我们不把范围设置为1呢？vs计数排序
桶类:为什么我们不把范围设置为1呢？vs计数排序
提问于 2015-05-31 19:12:31
桶排序在其中一个桶中创建k个buckets....and分布的n个数字。第1-10，11-20，21-30.O(n+k)
桶中的编号使用插入O(n平方)进行排序。
只有少数几个数字在同一个桶里才能正常工作。O(n+k)，但如果所有数字都在同一个桶中结束，则...O(n平方公里)
我的问题是，如果我们把桶的范围定为1，即0-1 ,1-2，2-3……不同的编号不会在同一个桶中结束.(不需要在桶中排序) O(n+k)
在不考虑空间复杂性的情况下，我们为什么不使用这个来代替计数排序呢？如果我错了请纠正我。
回答 2
Stack Overflow用户
回答已采纳
发布于 2015-05-31 21:10:42
您建议的是一种称为计数排序的分发排序，只有一个更简单的版本，您知道元素是不重复的，所以计数停止在1。它在时间上是非常有效的O(N+n)，但确实需要O(N)空间。
许多人在被要求对一副牌进行排序时，自然会使用这种方法:他们会把每一张牌送到桌子上的位置，形成4行13张牌。最后一步是逐行收集卡片。这里有N == n，因为这两个步骤都需要O(n)时间，所以排序非常有效。
当N变得比n大得多时，比方说你想按照它们的序列号排序一堆20美元的钞票，这个方法就变得完全不切实际了。
如果要对整数进行排序，则可以考虑另一种具有O(n)时间复杂性的方法:基排序。
Stack Overflow用户
发布于 2015-05-31 19:33:46
在第一种方法和你提出的方法中，k的值是不一样的。假设在第一种情况下(大小为10的桶)有N个数字，在第二种情况下，需要N/10桶，在第二种情况下，需要N个桶。根据n和n的相对值，k有一个可能不是k=1的最优解。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/30561593
复制相关文章
相似问题
腾讯云开发者
