2

我很难理解桶排序的基本概念，我希望有人能准确地向我澄清排序算法的作用以及它如何在 O(N) 时间内完成所需的结果（对内部容器进行排序）。此外，由于这似乎相当快，其他排序算法（如冒泡、插入或选择）有什么优势可以说服人们使用它们而不是桶排序？

这是我在网上找到的算法的实现。如果有人可以在他们的解释中引用这一点，我将不胜感激。

void binsort(std::vector<std::size_t>& A){
    std::vector<std::vector<std::size_t>> B(MAX + 1);
    for(std::size_t i = 0; i < SIZE; ++i){
        B[A[i]].push_back(A[i]);
    }
    std::size_t current = 0;
    for(std::size_t i = 0; i < MAX; ++i){
        for(auto item : B[i]){
            A[current++] = item;
        }
    }
}

谢谢您的帮助。

4

4 回答 4

3

我将尝试解释这个特定的实现，这是您可能会看到的最简单的实现之一。巧合的是，它也对输入域中允许的数字有严格的限制（由 value 表示MAX）。

假设我们有 10 个数字的集合。他们共享的一个属性是他们都在域中 [0..5]

{ 3, 2, 2, 5, 1, 4, 0, 2, 5, 4 }

现在，我们创建一个桶的“列表”，其中每个桶代表域中值的集合；不是输入数组。我们的域允许 6 个可能的值，因此我们创建了 6 个存储桶（按“顺序”排列，以防您没有注意到）：

 0: {}
 1: {}
 2: {}
 3: {}
 4: {}
 5: {}

现在遍历输入列表，将每个值放入它的存储桶中。从概念上讲，完成后它看起来像这样：

 0: {0}
 1: {1}
 2: {2,2,2}
 3: {3}
 4: {4,4}
 5: {5,5}

现在，只需遍历我们的存储桶列表，然后将每个存储桶中的内容转储回原始容器，替换那里的任何项目。

{ 0, 1, 2, 2, 2, 3, 4, 4, 5, 5}

看起来很简单，是吗？那么为什么不是每个人都这样做呢？好吧，考虑我们扩大问题。代替MAX6 个可能的值，我们将“值”设为1048576(2 20如果您想知道的话)，但将排序的项目数保持为 10。

现在，给出以下列表：

{ 3, 2, 2, 1048576, 1, 4, 0, 2, 5, 4 }

我们的“桶”列表如下所示：

 0: {0}
 1: {1}
 2: {2,2,2}
 3: {3}
 4: {4,4}
 5: {5}
 6: {}
 7: {}
 .....
 1048575: {}
 1048576: {1048576}

是的，超过一百万个桶来对十个数字进行排序，这一切都是因为这是我们问题域中允许的最大值。MAX显然，这对于大天花板是不可行的。将输入范围细分为可管理的集合将是解决此问题的可行解决方案（实际上，这本质上是基数排序的工作方式。

要回答你的最后一组问题，显然如果你有一个相当小的输入域，你将很难在排序速度上击败它。例如，如果我们有一组一千个数字，所有这些数字都在 中[0..9]，这将是快速的咆哮。再加上几个数量级，根本就没有可比性。然而，你付出的代价，沉重的代价，是一个受限制的输入域。随着域大小的增加，您必须从分桶算法的角度来处理它，并且当您这样做时，您开始朝着 O(NlogN) 的方向前进。鉴于此，有很多算法（堆排序、合并排序、快速排序等）都有自己的一套警告值得考虑。

一个明显“获胜”的地方：假设您必须对一百万个 8 位字符（定义为 中的值[0..255]）进行排序，您将找不到更快的算法来做到这一点。该域定义明确，非常易于管理，如果使用了适当的“桶”表（字面意思是计数器表），我看不出它被打败了。

于 2013-02-26T07:52:52.850 回答
0

这是维基百科提供的解释。我希望这已经足够了。

桶排序或 bin 排序是一种排序算法，它通过将数组划分为多个桶来工作。然后使用不同的排序算法或递归地应用存储桶排序算法对每个存储桶进行单独排序。它是一种分布排序，是基数排序的表亲，具有最高到最低有效数字风味。桶排序是鸽巢排序的一种推广。由于桶排序不是比较排序，因此 Ω(n log n) 下限不适用。计算复杂度估计涉及桶的数量。

桶排序的工作原理如下：

  1. 设置一组最初为空的“桶”。
  2. 分散：遍历原始数组，将每个对象放入其存储桶中。
  3. 对每个非空桶进行排序。
  4. 收集：按顺序访问桶，将所有元素放回原始数组中。
于 2013-02-26T06:38:10.963 回答
0

给出的解释很酷。那么，如果我们有负数，我们如何处理这种情况？一种解决方法是为负数保留一个单独的存储桶列表。

想象一下这个数据集：{ -5, -6, 5, 3, 6, -4 }

所以这里我们的“遗愿清单”如下：

清单 1：

0: {0}
1: {0}
2: {0}
3: {1}
4: {0}
5: {1}
6: {1}

遗愿清单 2：

-1: {0}
-2: {0}
-3: {0}
-4: {1}
-5: {1}
-6: {1}

因此，如果我们的案例仅涉及整数，我们的存储桶列表甚至不必包含其他列表。它们可以只是列表。

于 2013-03-24T18:25:20.407 回答
0

要处理负数的情况，您可以选择最小的负数并将该数添加到数组中的每个元素。 {-5,-6,5,3,6,-4}有最小的元素-6。将绝对值 -6 添加到数组中。数组现在是{1,0,11,9,12,2}然后用存储桶数组对其进行排序，它变成{0,1,2,9,11,12}并得到最终结果添加-6到每个，因此{-6,-5,-4,3,5,6}。就性能而言，这是可以的，因为数组的最低范围的减法和加法是 O(N)。

于 2015-11-04T03:18:12.823 回答