是什么让桶很好？
因此，我在非比较排序算法上遇到了绊脚石，准确地说，桶排序，我无法确切地理解为什么它是好的。
我有个想法，但我需要有人来确认。
让我们假设我想对一个1000个元素array.If进行排序，它是均匀分布的，并被放入10个桶中，其中每个桶都有100个元素。
使用n log(n)算法对100元素进行10次排序= 10 * 100 log(100) = 1000 log(100) = 2000
使用n log(n)算法对1000个元素进行排序时= 1000 log( 1000 ) = 3000
因此，该算法利用n=m+l，则(m+l)^2 > m^2 + l^2，同样适用于n个log(n)算法。
因此，数据越均匀，桶排序的性能就越好。
是这样吗？
桶的最佳数量是多少？(我觉得这是一种时空权衡，但也取决于数据排序的一致性)
回答 1
Stack Overflow用户
发布于 2020-05-11 08:11:30
但是你必须考虑到水桶步骤的复杂性是1000。这给了你：
1000 + 10 * 100 log(100) = 3000
- comparison
- 桶排序：排序：
1000 * log(1000) = 3000
但是，您可以再次应用存储策略来对较小的数组进行排序。我是https://en.wikipedia.org/wiki/Radix_sort。
所宣传的复杂性是O(n.w)，其中w是表示元素的位数。线性的？比合并排序好吗？等等，w通常有多大？是的，对于通常的集合，您必须使用log(n)位来表示元素，所以回到n log(n)。
正如您所说，这是一个时间/内存交易，而基数排序是当您有一个固定的内存预算(但谁没有呢？)如果您可以按照输入大小线性地增长内存，那么使用n存储桶，您就有了一个O(n)排序。
一个例子引用(有很多！)：https://www.radford.edu/nokie/classes/360/Linear.Sorts.html。
https://stackoverflow.com/questions/61724010
复制相似问题
腾讯云开发者
