什么使桶排序好？
所以我偶然发现了基于非比较排序的算法桶排序，确切地说，我不知道为什么它是好的。
我有一个想法，但我需要有人来证实。
假设我想对1000个元素数组进行排序。如果它被均匀地分配并扣入10个桶中，每个桶有100个元素。
使用n log（n）算法对100个元素进行10次排序=10*100 log（100）=1000 log（100）=2000
使用n log（n）算法对1000个元素进行排序时=1000 log（1000）=3000
所以这个算法利用了，如果n=ml，那么（ml）^2
因此，数据越均匀，桶排序的性能越好
是这样吗？
最佳的桶数是多少？（我觉得这是一个时空权衡的事情，但也取决于被排序的数据的一致性）
共有1个答案
但是，您必须考虑到bucketing步骤的复杂性为1000。这将为您提供：
- 桶排序：
1000 10*100日志（100）=3000 - 比较排序：
1000*日志（1000）=3000
但您可以再次应用bucketing策略对较小的数组进行排序。这是https://en.wikipedia.org/wiki/Radix_sort .
广告的复杂度是O（n.w），其中w是表示元素的位数。线性的比合并排序好？等一下，w通常有多大？是的，对于通常的数据集，您必须使用log（n）位来表示元素，所以回到nlog（n）。
正如您所说的，这是一种时间/内存交易，基数排序是指当您有固定内存预算时（但谁没有呢？）。如果您可以随着输入大小线性增长内存，那么使用nbucket，您就有了O（n）排序。
示例参考（有很多！）：https://www.radford.edu/nokie/classes/360/Linear.Sorts.html .
-
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点： 在额外空间充足的情况下，尽量增大桶的数量 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中 同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。 1. 什么时候最快 当输入的数据可以均匀的分配到每一个桶中。 2. 什么时候最慢 当输入
-
我正在用Java实现bucket排序，我发现当输入数组被排序（升序或降序）时，它的排序（升序）比随机排序快。为什么会这样？据我所知，它只是遍历数组，并在每个元素的索引处递增“tally”数组。我不明白为什么排序后的输入会运行得更快，但速度似乎是原来的两倍。 谢谢
-
主要内容：桶排序算法的实现思路,桶排序算法的具体实现桶排序（又称箱排序）是一种基于分治思想、效率很高的排序算法，理想情况下对应的时间复杂度为 O(n)。 接下来，我们系统地学习一下桶排序算法。 桶排序算法的实现思路 假设一种场景，对 {5, 2, 1, 4, 3} 进行升序排序，桶排序算法的实现思路是： 准备 5 个桶，从 1~5 对它们进行编号； 将待排序序列的各个元素放置到相同编号的桶中； 从 1 号桶开始，依次获取桶中放置的元素，得到的就是一
-
在elasticsearch中，是否有方法使用自定义分数对聚合桶进行排序/排序？ 我正在按客户姓名进行扣球。每个客户都有多个订单，其中有一个交货日期字段（DeliveDate）。我想根据与当前日期的距离（接近程度）对桶进行排序。 例如，对交货日期更接近今天日期的客户名进行排序。 非常感谢。
-
我想探讨我对桶排序的分析，如下所示 有许多方法可以实现桶排序。其中一些如下 类型1: 如果 时间： O（N） 空间： O（1） 类型2： 示例：按age age对一个人数组进行排序与用于排序的任意整数有些不同。正因为如此，它的范围[0-150]很小（所有人的年龄都在0-150之间）。因此，最快的排序方法是分配151个链表（让我们称之为桶），并根据每个人的年龄将其数据结构放入桶中： 时间：O（N K
-
拓扑排序主要解决的问题是给一个图的所有节点排序。 一、什么是拓扑排序 在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件： （1）每个顶点出现且只出现一次。 （2）若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。 有向无环图（