如果我们有N个整数，范围从1到M（或从0到M-1），我们可以利用这个信息得到一种快速的排序，叫做桶式排序（bucket sort）。我们留置一个数组，称之为Count，大小为M，并初始化为零。于是，Count有M个单元（或桶），开始时他们都是空的。当Ai被读入时，Count[Ai]增1。在所有的输入被读进以后，扫描数组Count，打印输出排好序的表。该算法花费O（M+N）。引自《数据结构与算法分析——C语言描述》
下面是对上述算法的更详细描述：
对于一组有界的整数，比如有N个数，它们的取值为[1,M]，那么对于这样的一组数的排序，可以使用桶式排序。假设这一组整数存储在一个数组A中，桶式排序的基本思想是维护一个count数组，这个数组有M个单位(相当于M个桶)，在读入A中的数据A[i]时，count[A[i]]加1，也即是把A[i]放进count的一个桶里，数据读取完成排序即完成。扫描count数组的元素，并顺序输出非0项的index(count[index]为多少就输出多少次)。很显然桶式排序的时间为扫描A数组N个元素的时间加上扫描count数组M个元素的时间，于是为O(M + N)。
#include <stdio.h> int find_max(int A[], int N) { int i, max; max = A[0]; for(i = 1; i < N; i++) { if(A[i] > max) max = A[i]; } return(max); } void bucket_sort(int A[], int N) { int i, M; M = find_max(A, N); int count[M + 1]; /* 下标从0开始，保证最大下标为数组A中的最大数值 */ for(i = 0; i <= M; i++) count[i] = 0; for(i = 0; i < N; i++) count[A[i]]++; for(i = 0; i <= M; i++) { while(count[i] > 0) { printf("%d ", i); count[i]--; } } printf("\n"); } int main(void) { int i; int A[] = {3, 2, 4, 5, 8, 1, 7, 6}; printf("before sorted: "); for(i = 0; i < 8; i++) printf("%d ", A[i]); printf("\n"); printf("after sorted : "); bucket_sort(A, 8); }
编译运行结果：
原文：http://www.cnblogs.com/nufangrensheng/p/3589526.html