algorithm - 为什么我们在桶排序中使用插入排序？

Question

桶排序是一种线性时间排序。

为什么要用插入排序呢？我们知道插入排序需要 O(n2) 的时间。为什么我们不能在其中使用任何线性排序？如我们所见，在每个桶中我们使用插入排序 O(n2)。桶排序的总复杂度 O(n) 是多少？为什么我们不使用 O(nlogn) 排序，例如归并排序或快速排序？

Answer 1

只有当我们可以预期每个桶中只有少数项目时，桶中插入排序的桶排序才是合理的。当只有少数项目时，插入排序就可以了。

在现实生活中，这种情况并不经常发生。通常是当我们期望数据均匀分布时，因为我们正在按哈希顺序或类似顺序进行排序。

桶排序最常用于整个排序——即，桶根本不需要排序，您只需将每个项目附加到桶列表中即可。

有时我们会进行自上而下的基数排序，这就像桶排序，然后对每个桶进行桶排序。结合保留非空桶的位掩码，当排序键为 32 位整数时，这可能是一种非常快速的排序方式。

您还可以通过对不同范围的位重复进行桶排序来进行自下而上的基数排序，并将项目附加到每个桶。这种桶排序是稳定的，所以当您按高位进行桶排序时，平局会被之前的排序打破，而这是您通过低位排序得到的。