为什么我们在Bucket排序中使用插入排序？

Question

存储桶排序是线性时间排序。

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

Answer 1

只有当我们可以预期每个存储桶中只有几个项目时，存储桶中的插入排序才是合理的。当只有几个项目时，插入排序是合适的。

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

存储桶排序最常用的情况是整个排序--也就是说，存储桶根本不需要排序，只需将每个项目追加到存储桶列表中即可。

有时我们做一个自上而下的基数排序，这就像桶排序，然后桶排序每个桶。与保留非emtpy存储桶的位掩码相结合，当排序关键字是32位整数时，这是一种非常快速的排序方法。

您还可以执行自下而上的基数排序，方法是在不同的位范围上重复存储桶排序，然后将项添加到每个存储桶中。这种存储桶排序是稳定的，所以当您按高位进行存储桶排序时，以前的排序会打破平局，这是通过对较低的位进行排序而获得的。

Answer 2

插入排序需要O(n2)时间。

这还不是故事的全部。对于部分排序的数组，插入排序的性能很好，它具有线性时间复杂度。

其中每个条目都离其最终位置不远的数组是部分排序数组的典型示例。这就是Bucket sort的情况。