桶式排序是一种常见的排序方法,其定义如下:
如果我们有N个整数,范围从1到M(或从0到M-1),我们可以利用这个信息得到一种快速的排序,叫做桶式排序(bucket sort)。我们留置一个数组,称之为Count,大小为M,并初始化为零。于是,Count有M个单元(或桶),开始时他们都是空的。当数组元素A[i]被读入时Count[A[i]]增1。在所有的输入被读进以后,扫描数组Count,打印输出排好序的表。该算法花费O(M+N)。
可见其应用需要满足下列条件:
所有待排序字段必须为非负且有界,即0 <= a[i] < M。
实际应用中很多字段都满足这个条件,如人的年龄,字符的种类(a-z)等等。
C语言实现如下:
#include <stdio.h> #include <assert.h> #define M 200 void BucketSort(const unsigned int array[], const unsigned int n) { unsigned int i, j; assert(NULL != array && n > 0); unsigned int bucket[M]; for(i = 0; i < M; ++i) { bucket[i] = 0; } for(i = 0; i < n; ++i) { // assert(array[i] < MAXVALUE); ++bucket[array[i]]; } for(i = 0; i < M; ++i) { for(j = 0; j < bucket[i]; ++j) { printf("%d\n", i); } } } int main(void) { unsigned int age[] = {3,1,4,1,5,9,2,6,5,3,5,8,9}; printf("Hello World!\n"); BucketSort(age, sizeof(age)/sizeof(age[0])); return 0; }