4

如果我们必须对 4 个数字中的 7 个数字进行排序，那么在最坏的情况下需要进行多少次比较？（基数排序）选项是 - 40,38,47,280。

我的解决方案——我拿了 10 个桶（0 到 9）（链表）。然后对于第 i 个数字的每个数字，我将其放入 Bucket 中，对应于其数字的值。然后我将这些数字收集到数组中。对所有数字重复此过程，因此我的原始数组已排序。比较总数= 10*4=40（10，因为我遍历了所有的桶来寻找对应的桶）。

现在问题出在蒂莫西·J·威廉姆斯（Timothy J Williams）的书中，给出的比较数=数字数*数字数*桶数=4 * 7 * 10 = 280。我无法理解。有人可以解释一下这是怎么回事。

4

1 回答 1

2

确实，基数排序不是基于比较的算法。这里的比较说明了迭代中涉及的比较。首先，我们需要遍历 7 个元素的数组，并将每个数字的位数保存在相应的桶中。这里为了遍历数组，我们需要 7 次比较。将所有元素放入 0-9 的桶中后，我们需要遍历 0-9 的所有桶，并根据它们的桶号排列元素，这需要 10 次比较才能遍历 0-9 的桶。现在我们必须对 7 个元素的所有 4 位重复这个过程。因此，比较总数为 7*10*4 = 280

于 2017-08-02T05:18:21.257 回答