桶排序
桶排序(Bucket Sort)的原理很簡(jiǎn)單痹仙，它是將數(shù)組分到有限數(shù)量的桶子里是尔。假設(shè)待排序的數(shù)組a中共有N個(gè)整數(shù)，并且已知數(shù)組a中數(shù)據(jù)的范圍[0, MAX)蝶溶。在桶排序時(shí)嗜历，創(chuàng)建容量為MAX的桶數(shù)組r，并將桶數(shù)組元素都初始化為0抖所；將容量為MAX的桶數(shù)組中的每一個(gè)單元都看作一個(gè)"桶"梨州。在排序時(shí)，逐個(gè)遍歷數(shù)組a田轧，將數(shù)組a的值暴匠，作為"桶數(shù)組r"的下標(biāo)。當(dāng)a中數(shù)據(jù)被讀取時(shí)傻粘，就將桶的值加1每窖。例如，讀取到數(shù)組a[3]=5弦悉，則將r[5]的值+1窒典。
swift
<pre>
func bucketSort(originArray: [Int]) -> [Int] {
let maxNum = originNum.max()
//桶的數(shù)目
var bucket:[Int] = Array.init(repeatElement(0, count: maxNum! + 1))
var newNum:[Int] = Array.init()
//給桶加標(biāo)記
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
}
//運(yùn)行結(jié)果
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 待排序數(shù)組
@param numMax 數(shù)組的最大值
-
@param count 數(shù)組元素個(gè)數(shù)
*/
bucket_sort(int num[],int numMax, int count)
{
//桶數(shù)目
int bucketNum = numMax + 1;
int bucket[bucketNum];
for (int i = 0; i < bucketNum; i++) {
bucket[i] = 0;
}//給桶加標(biāo)記
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);
}
}
}
//運(yùn)行結(jié)果
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>
