|
看到书上的桶排序，就写了一个，基本的思想如下：
This algorithm like Count Sort, once you know the range of the numbers,
then you can make them into the (0, 1) range. And divide the (0, 1) into 10
buckets, and then cram the numbers into the buckets which is suitable for
it. If the buckets less then the numbers, then you can fix every buckets with
the proper order of the numbers. That means put the numbers which are in
the same buckets into a single chain. Thus you have fixed the numbers.
Then we’ll output them in order. Put the buckets’ elements one by one.
Ignore the ones which don’t have elements in its buckets.
There are the implementation of the algorithm bellow.
运行方法：
gcc bucket.c
./a.out
就可以了。
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
const int N = 20;
const int M = 10;
struct chain
{
int key;
struct chain *next;
};
void initBucket(struct chain a[], int n)
{
int i = 0;
for(; i < n; i++)
{
a[i].key = i * 10;
a[i].next = NULL;
}
}
int * generate(int a[], int n)
{
int i;
for(i = 0; i < n; i++)
{
a[i] = 0;
}
time_t t;
srand((unsigned)time(&t));
for(i = 0; i < n; i++)
{
a[i] = rand() % 100;
}
return a;
}
void printArray(int *a, int n)
{
int i = 0;
while(i < n)
{
printf("%4d", a[i]);
i++;
}
printf("\n");
}
void printBucket(struct chain a[], int n)
{
int i = 0;
for(; i < n; i++)
{
printf("%4d", a[i].key);
}
printf("\n");
}
void insertChain(struct chain node, struct chain *newNode)
{
if(node.next == NULL)
{
node.next = newNode;
}
else
{
struct chain *p = node.next;
struct chain *q = p;
while(p->key < newNode->key)
{
q = p;
p = p->next;
}
newNode->next = q->next;
q->next = newNode;
}
}
void printKeys(struct chain a[], int n)
{
int i = 0;
for(; i < n; i++)
{
if(a[i].next != NULL)
{
struct chain *p = a[i].next;
while(p->next != NULL)
{
printf("%4d", p->key);
p = p->next;
}
printf("%4d", p->key);
}
}
}
void insertBucket(struct chain a[], int *keys, int n)
{
int i = 0;
for(; i < n; i++)
{
struct chain *newNode = (struct chain *)malloc(sizeof(struct chain));
newNode->key = keys[i];
newNode->next = NULL;
struct chain *node = &a[keys[i] / 10];
if(node->next == NULL)
{
node->next = newNode;
}
else
{
struct chain *p = node->next;
struct chain *q = p;
while((p->key <= newNode->key) && (p->next != NULL))
{
q = p;
p = p->next;
}
newNode->next = q->next;
q->next = newNode;
}
}
}
int main()
{
struct chain heads[M];
initBucket(heads, M);
printf("bucket: ");
printBucket(heads, M);
int keys[N];
generate(keys,N);
printf("numbers:");
printArray(keys, N);
insertBucket(heads, keys, N);
printf("ordered:");
printKeys(heads, M);
printf("\n");
return 0;
}
|
