1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| #include <stdio.h>
#include <stdlib.h>
#define ARRSIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define BUCKET_CAPACITY 10 //一个桶能装多少个元素
typedef struct Bucket
{
int values[BUCKET_CAPACITY];
int size; //数量
} Bucket, *PBucket;
void BSort(int elements[], int len, int bucketCapacity)
{
//寻找最大值和最小值
int max = elements[0];
int min = elements[0];
int i, j, k;
for (i = 0; i < len; i++)
{
if (max < elements[i])
max = elements[i];
if (min > elements[i])
min = elements[i];
}
int bucketCount = (max - min) / bucketCapacity + 1; //所需桶的数量
//初始化这些桶
PBucket buckets = (PBucket)malloc(sizeof(Bucket) * bucketCount);
for (i = 0; i < bucketCount; i++)
{
buckets[i].size = 0;
}
for (i = 0; i < len; i++)
{
//入桶
int mod = (elements[i] - min) / bucketCapacity;
buckets[mod].values[buckets[mod].size++] = elements[i];
}
//对每个桶进行排序
for (i = 0; i < bucketCount; i++)
{
//插入排序
for (j = 1; j < buckets[i].size; j++)
{
int tmp = buckets[i].values[j];
for (k = j; k > 0; k--)
{
if (buckets[i].values[k - 1] > tmp)
{
buckets[i].values[k] = buckets[i].values[k - 1];
}
else
break;
}
buckets[i].values[k] = tmp;
}
}
//桶中的数据放回序列
i = 0, j = 0, k = 0;
for (i = 0; i < bucketCount; i++)
{
for (j = 0; j < buckets[i].size; j++)
{
elements[k++] = buckets[i].values[j];
}
}
free(buckets);
}
void BucketSort(int elements[], int len)
{
BSort(elements, len, BUCKET_CAPACITY);
}
int main(int argc, char const *argv[])
{
int elems[] = {3, 4, 2, 1, 5, 9, 2, 1, 0, 22, 33, 5, 112, 11, 22, 55, 22, 61, 97};
int len = ARRSIZE(elems);
BucketSort(elems, len);
for (int i = 0; i < len; i++)
printf("%4d", elems[i]);
printf("\n");
return 0;
}
|