如何对包含负数的整数数组进行桶排序？
而且，存储桶排序和计数排序有什么区别？
值的存储桶排序
对负值使用 Bucket 排序只需要将每个元素映射到与要排序的最小值的距离成比例的存储桶。
例如，当对以下输入使用每个值的存储桶(如上所述(时，如下所示：
input array: {4, 2, -2, 2, 4, -1, 0}
min = -2
bucket0: {-2}
bucket1: {-1}
bucket2: {0}
bucket3: {}
bucket4: {2, 2}
bucket5: {}
bucket6: {4, 4}
建议的算法
#A: array to be sorted
#count: number of items in A
#max: maximal value in A
#min: minimal value in A
procedure BucketSort(A, count, max, min)
#calculate the range of item in each bucket
bucketRange = (max - min + 1) / bucketsCount
#distribute the item to the buckets
for each item in A:
bucket[(item.value - min) / bucketRange].push(item)
#sort each bucket and build the sorted array A
index = 0
for bucket in {0...bucketsCount}:
sort(bucket)
for item in {0...itemsInBucket}:
A[index] = item
index++
C++实施
请注意存储桶范围，它与最大值和最小值之间的范围成正比
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm> // std::sort
#include <stdlib.h> // rand
#include <limits> // numeric_limits
using namespace std;
#define MAX_BUCKETS_COUNT (10) // choose this according to your space limitations
void BucketSort(int * arr, int count, int max, int min)
{
if (count == 0 or max == min)
{
return;
}
// set the number of buckets to use
int bucketsCount = std::min(count, MAX_BUCKETS_COUNT);
vector<int> *buckets = new vector<int>[bucketsCount];
// using this range we will we distribute the items into the buckets
double bucketRange = (((double)max - min + 1) / (bucketsCount));
for (int i = 0; i < count; ++i)
{
int bucket = (int)((arr[i] - min) / bucketRange);
buckets[bucket].push_back(arr[i]);
}
int index = 0;
for (int i = 0; i < bucketsCount; ++i)
{
// here we sort each bucket O(klog(k) - k being the number of item in the bucket
sort(buckets[i].begin(), buckets[i].end());
for (vector<int>::iterator iter = buckets[i].begin(); iter != buckets[i].end(); ++iter)
{
arr[index] = *iter;
++index;
}
}
delete[] buckets;
}
测试代码
int main ()
{
int items = 50;
int data[items];
int shift = 15;//inorder to get some negative values in the array
int max = std::numeric_limits<int>::min();
int min = std::numeric_limits<int>::max();
printf("before sorting: ");
for (int i = 0; i < items; ++i)
{
data[i] = rand() % items - shift;
data[i] < min ? min = data[i]: true;
data[i] > max ? max = data[i]: true;
printf("%d ,", data[i]);
}
printf("n");
BucketSort(data, items, max, min);
printf("after sorting: ");
for (int i = 0; i < items; ++i)
{
printf("%d ,", data[i]);
}
printf("n");
return 0;
}
这基本上是一个仅链接的答案，但它为您提供了制定好问题所需的信息。
存储桶排序
维基百科的第1步，即"设置一个初始空桶的数组"，将需要包括负数的桶。
计数排序
"与计数排序相比，存储桶排序需要链表、动态数组或大量预分配内存来保存每个存储桶中的项目集，而计数排序则为每个存储桶存储单个数字(项目计数(。
桶排序或 bin 排序是一种排序算法，通过将数组的元素分布到多个存储桶中来工作。然后，使用不同的排序算法或通过递归应用存储桶排序算法对每个存储桶进行单独排序。
步骤：
-
设置一个初始为空的"存储桶"数组。
-
分散：遍历原始数组，将每个对象放入其存储桶中。
-
对每个非空存储桶进行排序。
-
收集：按顺序访问存储桶，并将所有元素放回原始数组中。
存储桶排序假定输入是从均匀分布中提取的，并且平均运行时间为 O(n(。计算复杂度估计涉及存储桶的数量。
最坏情况性能：O(n^2(
最佳表壳性能：欧米茄(n+k(
平均案例性能：θ(n+k(
最坏情况下的空间复杂度：O(n.k(
对于实现和象形理解：
http://javaexplorer03.blogspot.in/2015/11/bucket-sort-or-bin-sort.html
存储桶排序需要一个有序字典，其中唯一值作为键，其各自的频率作为值。这是第一行的作用，并将此字典分配给 k。
第二行返回一个使用双列表推导的 python 列表，以输出有序的键"频率"时间。总和(...， []( 扁平化
neglist = [-1, 4, 5, 6, 7, 3, 4, 3, 2, 5, 8, -2, 7, 8, 0, -3, 7, 3, 7, 3, 1, 15, 12, 4, 5, 6, 7, 3, 1, 15]
poslist = [4, 2, 7, 9, 12, 3, 7]
def bucket(k):
k = dict((uni, k.count(uni)) for uni in list(set(k)))
return sum(([key for i in range(k.get(key))] for key in sorted(k.keys())), [])
print("NegList: ", bucket(neglist))
print("PosList: ", bucket(poslist))
'''
NegList: [-3, -2, -1, 0, 1, 1, 2, 3, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 7, 7, 7, 7, 7, 8, 8, 12, 15, 15]
PosList: [2, 3, 4, 7, 7, 9, 12]
'''