# 工学1号馆

home

## 桶排序算法

Wu Yudong    July 26, 2016     Algorithm   639

1. 设置一个定量的数组当作空桶子。
2. 寻访序列，并且把项目一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把项目再放回原来的序列中。

function bucket-sort(array, n) is
buckets ← new array of n empty lists
for i = 0 to (length(array)-1) do
insert array[i] into buckets[msbits(array[i], k)]
for i = 0 to n - 1 do
next-sort(buckets[i])
return the concatenation of buckets[0], ..., buckets[n-1]

// Completed on 2014.10.13 12:20
// Language: C99
//
// 版权所有（C）wuyudong
// 博客地址：http://www.wuyudong.com
#include<stdio.h>
#include<stdlib.h>

typedef struct node {
int value;
struct node * next;
}node, *pnode;

void bucketSort(int a[], node bucket[], int n)
{
int i = 0;
pnode tmp, t;
for(i = 0; i < n; i++) {
tmp = &bucket[a[i] / 10];
t = (pnode)malloc(sizeof(node));
t->value = a[i];
t->next = NULL;
while(tmp != NULL) {
if(tmp->next == NULL) {
t->next = tmp->next;
tmp->next = t;
break;
} else if (tmp->next->value > t->value) {
t->next = tmp->next;
tmp->next = t;
break;
} else {
tmp = tmp->next;
}
}
}
}

int main()
{
node bucket[10];
pnode tmp;
int a[] = {12, 22, 34, 24, 24, 56, 77, 87, 15, 28, 57, 99};
int size = sizeof(a) / sizeof(a[0]);
for(int i = 0; i < 10; i++)
bucket[i].next = NULL;
bucketSort(a, bucket, size);
for(int k = 0; k < 10; k++) {
tmp = bucket[k].next;
while(tmp != NULL) {
printf("%d ", tmp->value);
tmp = tmp->next;
}
}
printf("\n");
return 0;
}