我正在寻找采取一个整数数组，并在该阵列上执行部分桶排序。桶中的每个元素都小于当前的桶元素。例如，如果我有10个存储桶，其值为0-100 0-9将在第一个存储区中执行，而第二个存储区将执行10-19，依此类推。如何从数组中创建严格排序的均匀分布桶？
举个例子，我可以把1 12 23 44 48放到4个桶中，但是如果我有1,2,7,4,9,1，那么所有的值都会进入一个桶。我正在寻找一种在保持排序的同时将值均匀分配给所有存储桶的方法。每个存储桶中的元素不必进行排序。例如，我看起来与此类似。
2 1 9 2 3 8 7 4 2 8 11 4 => [[2,1]，[2,2]，[3]，[4]，[4]，[7]，[ 8]，[9]，[11]]
我试图使用此作为一种快速的方法来分区映射减少列表。
感谢您的帮助。
编辑，也许这将清除的东西了：
我想去的地方在bucket1 < bucket2 < bucket3所有元素......，其中每个桶是无序创建一个散列函数。
如果我正确地理解了它，则需要大约100TB的数据或13,743,895,347,200个未签名的64位整数，并且要通过多个存储桶进行分配。
第一步可能是对输入进行迭代，看例如，每个整数的最高24位，并对它们进行计数。这将给你一个16,777,216个范围的列表，每个范围的平均数为819,200，所以它可能存储在32位无符号整数中，这将占用64 MB。
然后，您可以使用它创建一个查询表，告诉您这16,777,216个范围中的每个范围都会进入哪个存储区。您可以计算每个存储桶中应该有多少整数（输入大小除以存储桶数量），然后遍历阵列，保持计数总数，并将每个范围设置为存储桶1，直到运行总量过多对于存储区1，则将范围设置为存储区2，依此类推......
当然总会存在必须在存储区n和存储区n + 1之间进行拆分的范围。为了跟踪这一点，你需要创建第二个表格来存储这些分割范围中有多少个整数应该进入第n + 1个分区。
所以，你现在已经例如：
HIGH 24-BIT RANGE BUCKET BUCKET+1
0 0 ~ 2^40-1 1 0
1 2^40 ~ 2*2^40-1 1 0
2 2*2^40 ~ 3*2^40-1 1 0
3 3*2^40 ~ 4*2^40-1 1 0
...
16 16*2^40 ~ 17*2^40-1 1 0
17 17*2^40 ~ 18*2^40-1 1 284,724 <- highest 284,724 go into bucket 2
18 18*2^40 ~ 19*2^40-1 2 0
...
您现在可以遍历再次输入，并为每个整数看看最高的24位，并使用查找表，看看哪个桶整数应该进入。如果范围没有分割，您可以立即将整数移动到右边的桶中。对于每个拆分范围，创建一个有序列表或优先级队列，该队列可以保存需要进入下一个存储桶的整数;您只在此列表或队列中存储最高值;任何较小的整数都会直接进入存储区，并且如果将整数添加到完整列表或队列中，则最小值将移至存储区。最后，这个列表或队列被添加到下一个存储桶中。
范围的数量应尽可能使用可用内存，因为这样可以最大限度地减少拆分范围中的整数数量。通过大量输入，您可能需要将分割范围保存到磁盘，然后分别单独查看每个分割范围，找到最高x值，然后相应地将它们移动到分区。
第一次运行时，其复杂度为N，然后在迭代遍历输入时再遍历范围R，然后遍历N，然后对于拆分范围，您将有类似M.logM的东西进行排序和M进行分配，所以总共为2 * N + R + M.LogM + M.使用大量范围来保持低分割范围内的整数数量可能是加快处理速度的最佳策略。
实际上，这是在分割范围的整数的数目M取决于水桶B的数目并且为R，其中M = N × B/R，以使得例如有千桶和一百万个范围，0.1％的输入将在分割范围内并且必须被分类。 （这些是平均值，具体取决于实际分配情况。）这使得总的复杂性2 × N + R +（N × B/R）.Log（N × B/R）+ N × B/R。
又如：
输入：N = 13,743,895,347,200无符号64位整数
范围：2 （使用每个整数的最高32位）每范围
整数：3200（平均）
计数列表：2 16位整数= 8 GB
查找表：2 16位整数= 8 GB
分程表：乙16位整数= 2 ×乙字节
随着1024桶，这将意味着，B/R = 1/2 ，并且有1023分裂与3200左右的范围内的整数每个或总共大约3,276,800个整数;这些将不得不被分类并分配到桶中。
使用1,048,576个桶，这将意味着B/R = 1/2 ，并且有1,048,575个分割范围，每个分割范围大约有3200个整数，总共约为3,355,443,200个整数。 （超过65,536个桶当然需要一个32位整数查找表）。
（如果您发现每个范围的总计数不等于输入的总大小，溢出计数列表中，您应该切换到一个更大的整数类型计数）
让我们通过一个很小的例子运行：在区间1-100分50个整数必须分布在5桶。我们选择了一些范围，比如20，并逐一输入来算整数每个范围内的号码：
2 9 14 17 21 30 33 36 44 50 51 57 69 75 80 81 87 94 99
1 9 15 16 21 32 40 42 48 55 57 66 74 76 88 96
5 6 20 24 34 50 52 58 70 78 99
7 51 69
55
3 4 2 3 3 1 3 2 2 3 5 3 0 4 2 3 1 2 1 3
然后，知道每个桶应该持有10个整数，我们遍历计数的列表每范围，每个范围分配给一斗：
3 4 2 3 3 1 3 2 2 3 5 3 0 4 2 3 1 2 1 3 <- count/range
1 1 1 1 2 2 2 2 3 3 3 4 4 4 4 5 5 5 5 5 <- to bucket
2 1 1 <- to next
当一个范围内有两个桶之间被分割，我们将它应该去的下一桶在一个单独的表整数数量。我们可以再次迭代输入，并将所有在非分割范围内的整数移入桶中;在分割范围的整数被暂时转移到单独的水桶：
bucket 1: 9 14 2 9 1 15 6 5 7
temp 1/2: 17 16 20
bucket 2: 21 33 30 32 21 24 34
temp 2/3: 36 40
bucket 3: 44 50 48 42 50
temp 3/4: 51 55 52 51 55
bucket 4: 57 75 69 66 74 57 57 70 69
bucket 5: 81 94 87 80 99 88 96 76 78 99
然后我们来看看温水桶一个接一个，发现X最高整数作为第二个表显示，其移动到下一桶，和剩下到从前的水桶：
temp 1/2: 17 16 20 (to next: 2) bucket 1: 16 bucket 2: 17 20
temp 2/3: 36 40 (to next: 1) bucket 2: 36 bucket 3: 40
temp 3/4: 51 55 52 51 55 (to next: 1) bucket 3: 51 51 52 55 bucket 4: 55
而最终的结果是：
bucket 1: 9 14 2 9 1 15 6 5 7 16
bucket 2: 21 33 30 32 21 24 34 17 20 36
bucket 3: 44 50 48 42 50 40 51 51 52 55
bucket 4: 57 75 69 66 74 57 57 70 69 55
bucket 5: 81 94 87 80 99 88 96 76 78 99
所以，出的50个整数，我们不得不进行排序一组3,2和5 intege RS。
其实，你并不需要创建一个表整数的应该进入下一个水桶分割范围内的号码。您知道每个存储桶应该有多少个整数，因此在初始分配之后，您可以查看每个存储桶中已有多少个整数，然后从分解范围中添加必需数量的（最低值）整数。在上面的例子，这预计每铲斗10点的整数，这将是：
3 4 2 3 3 1 3 2 2 3 5 3 0 4 2 3 1 2 1 3 <- count/range
1 1 1/2 2 2/3 3/4 4 4 4 5 5 5 5 5 <- to bucket
bucket 1: 9 14 2 9 1 15 6 5 7 <- add 1
temp 1/2: 17 16 20 <- 3-1 = 2 go to next bucket
bucket 2: 21 33 30 32 21 24 34 <- add 3-2 = 1
temp 2/3: 36 40 <- 2-1 = 1 goes to next bucket
bucket 3: 44 50 48 42 50 <- add 5-1 = 4
temp 3/4: 51 55 52 51 55 <- 5-4 = 1 goes to next bucket
bucket 4: 57 75 69 66 74 57 57 70 69 <- add 1-1 = 0
bucket 5: 81 94 87 80 99 88 96 76 78 99 <- add 0
如何输入的多将在分割范围和需要的计算要排序的，上面给出的作为M = N × B/R，是大致均匀分布的输入的平均值。稍有偏差，在输入空间的某个部分具有更多值将不会产生太大影响，但确实可以制定最坏情况输入来阻止算法。
让我们再在该实施例中的外观：
输入：N = 13,743,895,347,200无符号64位整数
范围：2 （使用每个整数的最高32位）每范围
整数：3200（平均）
铲斗：每桶1,048,576
整数：13107200
首先，如果整数范围包含多于2个整数，则必须将64位整数用于计数表，因此它的大小为32GB，这可能会迫使您使用更少的范围，具体取决于可用内存。
此外，每个存储区的整数大于每个存储区的目标大小的自动分隔范围。因此，如果整数分布在很多本地群集中，那么您可能会发现大部分输入都在需要排序的分割范围内。
如果你有足够的内存来运行使用2- 范围中的第一个步骤，则每个范围具有2 不同的值，你可以分发分割范围并且使用计数排序桶（其具有线性复杂）。
如果您没有内存使用范围，并且最终出现问题的大分割范围，则可以在分割范围上再次使用完整算法。假设您使用了2个范围，期望每个范围能够保持大约51,200个整数，并且最终会出现一个意想不到的大分割范围，其中需要分配391个桶，需要5,120,000,000个整数。如果你在这个有限的范围内再次运行该算法，那么只需391个桶就可以得到一个范围（每个范围平均拥有19个整数，最多有16个不同的值），并且只有很小的风险才会以大再次分割范围。
哇这是一个惊人的答案。我很好奇你是如何严格控制它的。似乎您几乎需要对每个存储桶进行排序以查找每个存储桶的最大值以便碰到下一个存储桶。每个单一元素具有相同的值时会发生什么？这仍然会有效平衡它吗？ – user3509528
@ user3509528嗯，重点是你需要使用比有桶的更多的范围;如果你有例如100倍于桶的范围，只有1％的输入需要排序。但确实，这是一个平均值，对于大致均匀分布的输入，有可能故意制造最坏情况的输入。我会扩大解决这个问题的答案。 – m69
顺便说一句，你会使用多少桶，什么是内存限制，你是否希望输入中有很多重复值或任何其他已知的偏差？ – m69
是否需要比O（N.LogN）更高效？否则，您可以先对数组进行排序，然后将其分布到存储桶中。另外，你知道数组中有多少个整数，它们的值范围是什么？ – m69
@ m69，需要更快。我正在研究传播整个频谱的100TB随机数据。它是地图操作的一部分，但不能保证被平等分割。 – user3509528
我用另一个例子更新了我的答案。这是否适用于您的问题？ – m69