1.桶式排序
桶式排序算法描述：如果我们有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)。
基于数组实现:
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); }
2.基数排序
基数排序是桶式排序的推广.设有10个数范围在0-999之间,我们将其排序.显然我们不能使用桶式排序,那样桶会太多.此时我们的策略就是多趟桶式排序.算法就是先对最低(有效)"位"进行桶式排序,然后对次低有效位进行桶式排序.....当然有可能有多余一个数落入相同的桶当中,因此我们把他们放入到一个链表当中
网友评论