桶排序是一种线性时间排序。
为什么我们要在其中使用插入排序呢？我们知道插入排序需要O(n2) 时间。 为什么我们不能在其中使用任何线性排序？ 正如我们所看到的，当我们在每个桶中使用插入排序时，其复杂度为O(n2)。那么为什么桶排序的总复杂度是O(n) 呢？ 为什么我们不使用O(nlogn) 的排序算法，如归并排序或快速排序？
2个回答
6
使用插入排序的桶排序只有在我们可以预期每个桶中只有少量项目时才是合理的。当只有少量项目时，插入排序是可以接受的。
在现实生活中，这种情况并不经常发生。通常是当我们期望数据均匀分布时，因为我们正在按哈希顺序或类似方式进行排序。
桶排序最常用于整个排序过程，即桶根本不需要排序，您只需将每个项目附加到桶列表中。
有时我们会进行自上而下的基数排序，这类似于桶排序，然后对每个桶进行桶排序。结合保持非空桶的位掩码，这可以是一种非常快速的排序32位整数排序键的方法。
您还可以通过重复在不同范围的位上进行桶排序并仅将项目附加到每个桶来进行自下而上的基数排序。这种类型的桶排序是稳定的，因此当您按高位进行桶排序时，绑定是由先前的排序顺序打破的，您通过低位排序获得了该顺序。
在现实生活中，这种情况并不经常发生。通常是当我们期望数据均匀分布时，因为我们正在按哈希顺序或类似方式进行排序。
桶排序最常用于整个排序过程，即桶根本不需要排序，您只需将每个项目附加到桶列表中。
有时我们会进行自上而下的基数排序，这类似于桶排序，然后对每个桶进行桶排序。结合保持非空桶的位掩码，这可以是一种非常快速的排序32位整数排序键的方法。
您还可以通过重复在不同范围的位上进行桶排序并仅将项目附加到每个桶来进行自下而上的基数排序。这种类型的桶排序是稳定的，因此当您按高位进行桶排序时，绑定是由先前的排序顺序打破的，您通过低位排序获得了该顺序。
- Matt Timmermans
1
插入排序需要O(n2)的时间。
但这并不是全部。对于部分有序的数组，插入排序表现良好，它具有线性时间复杂度。
每个条目都离其最终位置不远的数组是部分有序数组的典型示例。这就是桶排序的情况。
但这并不是全部。对于部分有序的数组，插入排序表现良好，它具有线性时间复杂度。
每个条目都离其最终位置不远的数组是部分有序数组的典型示例。这就是桶排序的情况。
- Yu Hao
2
为什么我们在桶排序中不使用任何线性排序（例如计数、基数等）？ - Jawwad Rafiq
我们如何确定它们部分排序并且彼此之间不远？
如果我们有大小为n的数组和桶数m。那么每个桶平均会有n/m个元素。它们可能以降序的方式出现在桶中，例如(10, 9, 8, 7, 6)，而我们需要最终结果是升序的。
因此，对于每个桶进行排序将需要n/m^2的时间。因此总时间复杂度为(n/m)^2 * m，即n^2。那么为什么桶排序是线性的呢？ - Vyacheslav Babanin
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接