桶排序中的桶索引
我正在尝试改进我的桶排序，以处理超过 10000 的大数。我不太确定为什么我的代码在大数上表现不佳。 我的大小为 n 的数组的桶排序算法：
- 创建大小为 n 的链表数组
计算数字范围
计算每个桶的间隔
- 计算桶的索引，在哪里放置特定的数字 （问题：我通过不断从数字中减去间隔并递增计数器来计算索引，每次减去间隔。计数器就是索引） 我相信这种查找索引的特殊方法对于大量数据来说需要很长时间。 如何改进桶的查找索引？
PS我听说有一种方法可以预处理数组并找到数组的最小和最大数量。然后通过从最小值中减去特定数字来计算索引。索引=数字-最小值我不太明白计算指数的想法。 问题： 1. 这是查找索引的有效方法吗？ 2. 当我的数组大小为 4、数字为 31、34、51、56 时，如何处理？ 31进入桶0，34进入桶3，51和56怎么样？ 3.还有其他计算指数的方法吗？
I'm trying to improve my bucket sort for large number over 10000.I'm not quite sure, why my code isn't performing well on large numbers.
My Bucket Sort algorithm for array of size n:
- Create array of linked list of size n
Calculate range for numbers
Calculate interval for each bucket
- Calculate index for bucket, where to put particular number
(Problem: I calculated index by constantly subtracting interval from number and increment counter,every time i subtract interval.Counter is the index)
I believe this particular way of finding index takes very long for large numbers.
How can i improve finding index of buckets?
P.S. i heard there's way to preprocess array and find min and max number of array. Then calculate index by subtracting particular number from min. index=number-min. I didn't quite get the idea of calculating index.
Questions:
1. Is this efficient way to find index?
2. How do i handle cases when i have array of size 4, and numbers 31,34,51,56? 31 goes to bucket 0,34 goes to bucket 3, how about 51 and 56?
3. Is there any other way to calculate index?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
通过除法你可以更快的找到你的索引。指数=值/区间。如果第一个间隔从“min”而不是 0 开始，则使用 (value-min) 作为分子。
You can find your index faster through Division. Index = value / interval. If the first interval starts at 'min' instead of 0, then use (value-min) as the numerator.