}
void countSort(int input[], int output[], int n, int d)
{
int i;
int digit;
for(i = 1; i <= n; i++)
{
digit = getDigit(input[i],d);
count[digit] = count[digit] +1;
}
for(i = 1; i <= K; i++)
{
count[i] = count[i-1] + count[i];
}
for(i = n; i >= 1; i--) //form large to small to make sorting stable
{
digit = getDigit(input[i],d);
output[count[digit]] = input[i];
count[digit]--;
}
}
void initDataStruct(int count[])
{
for(int i= 0; i < K; i++)
{
count[i] = 0;
}
}
void radixSort(int output[][N+1], int n, int d)
{
for(int i = 1; i <= d; i++)
{
countSort(output[i-1], output[i], n, i);
initDataStruct(count);
}
}
int main()
{
radixSort(output, N, D);
print(output[D], N);
return 0;
}
#include
#include
const int N = 7;
const int D = 3;
const int K = 10;
int count[K] = {0};
//int input[N+1] = {-1, 329, 457, 657, 839, 436, 720, 355};
int output[D+1][N+1]={{-1, 329, 457, 657, 839, 436, 720, 355}};
void print(int array[], int n)
{
for(int i = 1; i <=n; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
int getDigit(int number, int d)
{
if(d > D)return -1;
return number%(int)pow(10,d) / (int)pow(10,d-1);
}
void countSort(int input[], int output[], int n, int d)
{
int i;
int digit;
for(i = 1; i <= n; i++)
{
digit = getDigit(input[i],d);
count[digit] = count[digit] +1;
}
for(i = 1; i <= K; i++)
{
count[i] = count[i-1] + count[i];
}
for(i = n; i >= 1; i--) //form large to small to make sorting stable
{
digit = getDigit(input[i],d);
output[count[digit]] = input[i];
count[digit]--;
}
}
void initDataStruct(int count[])
{
for(int i= 0; i < K; i++)
{
count[i] = 0;
}
}
void radixSort(int output[][N+1], int n, int d)
{
for(int i = 1; i <= d; i++)
{
countSort(output[i-1], output[i], n, i);
initDataStruct(count);
}
}
int main()
{
radixSort(output, N, D);
print(output[D], N);
return 0;
}
三、桶排序
1、问题描述：假设输入数组有一个随机过程产生，该过程将元素均匀地分布在区间 [0, 1)上，对这个输入数组进行排序
2、基本思想：类似于散列表中解决散列冲突的拉链法，一个桶本质就是一个链表，将相同关键字的元素会被放入同一个桶中。由于输入数组中的元素均匀且独立均匀分布在 [0, 1)上，所以一般不会有很多个元素被分到同一个桶中去。散列完成后，先对各个桶中的元素进行排序，然后按次序把各桶中的元素收集出来即得到一个有序的数组。
3、算法描述：
输入：A[1...n]；B[0...n-1]：辅助数组链表，用于散列元素
输出：排序好的A[1...n]
（1）把区间 [0, 1) 划分成 n个相同大小的子区间，或称为桶（可用辅助数组链表B[0...n-1) 实现之）。
（2）已知，散列函数为：f(x) = floor(n*x) ， 向下取整，则数组元素A[i] 分配至 桶（链表）B[floor(n*A[i])]中 ---@(n)
（3）分别对每个桶B[i]中的元素进行排序（可用插入排序实现之） ---n*O(2-1/n)
（4）按次序收集各桶中的结果。
4、时间复杂度：根据3中的算法描述部分可知，除了第（3）步外，其他各部分在最坏情况下的时间都是O(n)。运用数理统计的知识可以求得，第（3）步中的对每个桶进行排序，运行时间的期望值为：2-1/n（详见：《算法导论》8.4节,P103），则第（3）步的总时间：n*(2-1/n)，故桶排序的期望运行时间：@(n) + n*(2-1/n) =@(n)
5、算法实现：
[cpp]
#include
#include
const int N =10;
double input[N+1] = {-1, 0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
typedef struct BucketNode
{
double data;
struct BucketNode* next;
}* bucketList, bucketNode;
bucketList bucketArr[N];
void print(bucketList bucketArr[])
{
for(int i = 0; i < N; i++)
{
bucketNode* pb = bucketArr[i];
while(pb)
{
printf("%e ", pb->data);
pb = pb->next;
}
printf("\n");
}
printf("\n");
}
void initBucketList(bucketList bucketArr[])
{
for(int i = 0; i < N; i++)
{
bucketArr[i] = NULL;
}
}
bool insertBucketWithSorting(bucketList& bucket, double data)
{//sorting while inserting
bucketNode* pb = new bucketNode;
if(NULL == pb)
r