桶排序
桶排序(Bucket Sort)的原理很简单，它是将数组分到有限数量的桶子里。假设待排序的数组a中共有N个整数，并且已知数组a中数据的范围[0, MAX)。在桶排序时，创建容量为MAX的桶数组r，并将桶数组元素都初始化为0；将容量为MAX的桶数组中的每一个单元都看作一个"桶"。在排序时，逐个遍历数组a，将数组a的值，作为"桶数组r"的下标。当a中数据被读取时，就将桶的值加1。例如，读取到数组a[3]=5，则将r[5]的值+1。
swift
<pre>
func bucketSort(originArray: [Int]) -> [Int] {
let maxNum = originNum.max()
//桶的数目
var bucket:[Int] = Array.init(repeatElement(0, count: maxNum! + 1))
var newNum:[Int] = Array.init()
//给桶加标记
for index in originNum {
let numId = index
bucket[numId] += 1
}
for index in bucket.indices {
while bucket[index] > 0 {
newNum.append(index)
bucket[index] -= 1
}
}
return newNum
}
//运行结果
let originNum :[Int] = [2,3,45,7,17,99,25,25,14,75,48,14,2,3,7,17]
let newNum = bucketSort(originArray: originNum)
print(newNum)
//[2, 2, 3, 3, 7, 7, 14, 14, 17, 17, 25, 25, 45, 48, 75, 99]**
</pre>
C
<pre>
/**
桶排序
@param num 待排序数组
@param numMax 数组的最大值
-
@param count 数组元素个数
*/
bucket_sort(int num[],int numMax, int count)
{
//桶数目
int bucketNum = numMax + 1;
int bucket[bucketNum];
for (int i = 0; i < bucketNum; i++) {
bucket[i] = 0;
}//给桶加标记
for (int i = 0; i < count; i++) {
int numId = num[i];
bucket[numId]++;
}for (int i = 0; i < numMax; i++) {
for (int j = 1; j <= bucket[i] ; j++) {
printf("%d \n",i);
}
}
}
//运行结果
int num[] = {2,3,45,7,17,99,25,25,14,75,48,14,2,3,7,17};
int count = sizeof(num) / sizeof(int);
bucket_sort(num,100,count);
//2,2,3,3,7,7,14,14,17,17,25,25,45,48,75,99,Program ended with exit code: 0
</pre>
