关于第二种桶排序中“c”参数的一些问题

1

用户传 c 还是 B 是一个设计问题，都可以。如果用户传 B，也需要在内部计算 c。

2

说的非常正确。这是桶排序的一个局限性。桶排序使用有一个前提条件就是：数据分布要相对均匀。（印象中课程里提到过这一点）否则就会出现过多元素集中在少数几个桶里，导致算法退化。

桶排序对此没有解决方案。如果你的数据分布不均匀，就不适合使用桶排序，应该转用其他排序算法。

==========

对于问题 2 的解释，也可以反过来去看你的问题 1。如果你的数据相对均匀，如果用户传入的是 c，就能保证每个桶中的元素个数最多在 c 附近。因此 c 这个参数能更好地**直接**帮助用户掌控整个算法的性能。而 B 不具有这个功能。

举个可能不完全恰当的例子：你有一家银行，你知道每个业务员每天最多处理 c 个业务的话，你就能根据每天银行会来多少人，决定当天需要多少个业务员上岗（B）。但如果你先指定 B，就要反着根据人数求一下每个业务员需要处理多少任务(c)，然后看这个任务量是不是超负荷了。如果超负荷了，还要再调整 B，反而是多了一步计算。

也就是当你传入的是 B，可能计算出 c 是 1000000，就很可能性能不够；但如果传入的 c = 10，在数据分布均匀的情况下，基本上每个桶的元素最多就是 10 左右，保证了性能肯定够。当然，这里有一个前提：数据分布是相对均匀的。

不过依然是，这是一个设计问题。实际上根据具体的情况，确实会有使用 B 更方便的情况。其实 B 决定的是空间，B 越大，耗的空间越多。所以如果空间是一个重要考虑因素的话，使用 B 就是更合适的。同时如果需要的空间过大，开辟这些空间的时间就不能忽略（尤其是在仅做依次排序的情况下），也会一定程序拖慢时间。

或许也正是因为这些限制，桶排序这个算法本身用于排序其实并不常见。但“桶”是一个很重要的算法思想，即把数据分组处理后，再整合。

上一章介绍的哈希表和 SQRT 分解就是这类思想。哈希表最典型，相当于同一个哈希值的元素是一个桶。更进一步，一些更巧妙地算法也在使用这类思想，比如 Mo's Algorithm（这个课程没有介绍，属于竞赛才会用到的算法了，面试一定不会涉及，感兴趣可以搜索查询自学一下）

继续加油！：）