是什么让桶排序好？
What make Bucket Sort good?
所以我无意中发现了基于非比较排序的算法，确切地说是桶排序，我无法确切地理解它为什么好。
我有一个想法，但我需要有人确认。
假设我想对 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) 算法
所以数据分桶越均匀，分桶排序的性能就越好
这样对吗？
最佳桶数是多少？ （我觉得这是一个 space 时间权衡的事情，但也取决于被排序数据的一致性）
但是你必须考虑到分桶步骤的复杂度为 1000。
这给你：
- 桶排序：
1000 + 10 * 100 log(100) = 3000
- 比较排序：
1000 * log(1000) = 3000
但是您可以再次重新应用分桶策略来对较小的数组进行排序。这是 https://en.wikipedia.org/wiki/Radix_sort .
广告的复杂度为 O(n.w)，其中 w 是表示元素的位数。线性？比合并排序更好？等一下，w 通常有多大？是的，对于通常的东西，你必须使用 log(n) 位来表示元素，所以回到 n log(n).
正如您所说，这是一个 time/memory 交易，而基数排序是当您有固定的内存预算时（但谁没有呢？）。如果你的内存可以随着输入大小线性增长，那么取 n 个桶，你就有了 O(n) 排序。
示例参考（有很多！）：https://www.radford.edu/nokie/classes/360/Linear.Sorts.html .
所以我无意中发现了基于非比较排序的算法，确切地说是桶排序，我无法确切地理解它为什么好。
我有一个想法，但我需要有人确认。
假设我想对 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) 算法
所以数据分桶越均匀，分桶排序的性能就越好
这样对吗？
最佳桶数是多少？ （我觉得这是一个 space 时间权衡的事情，但也取决于被排序数据的一致性）
但是你必须考虑到分桶步骤的复杂度为 1000。 这给你：
- 桶排序：
1000 + 10 * 100 log(100) = 3000 - 比较排序：
1000 * log(1000) = 3000
但是您可以再次重新应用分桶策略来对较小的数组进行排序。这是 https://en.wikipedia.org/wiki/Radix_sort .
广告的复杂度为 O(n.w)，其中 w 是表示元素的位数。线性？比合并排序更好？等一下，w 通常有多大？是的，对于通常的东西，你必须使用 log(n) 位来表示元素，所以回到 n log(n).
正如您所说，这是一个 time/memory 交易，而基数排序是当您有固定的内存预算时（但谁没有呢？）。如果你的内存可以随着输入大小线性增长，那么取 n 个桶，你就有了 O(n) 排序。
示例参考（有很多！）：https://www.radford.edu/nokie/classes/360/Linear.Sorts.html .