数据结构和算法

常用的排序算法（八）——桶排序

桶排序算法对待排数列有一定的要求。数据长度必须一样，并且符合均匀分布。

桶排序的基本思想就是先创建一个含n个元素的数组，即就是创建n个桶。然后将待排的数进行哈希算法并链接到这个数组的各个元素中去，即就是将这些数分布到各个桶中去。为得到结果先对各个桶中的数据进行排序，然后按次序把各个桶的元素取出来即可。

代码如下：

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#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 init_bucket(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 print_array(int *a, int n)
{
    int i = 0;
    while(i < n)
    {
        printf("%4d", a[i]);
        i++;
    }
    printf("\n");
}

void print_bucket(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 print_keys(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 insert_bucket(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];
    init_bucket(heads, M);
    printf("bucket: ");
    print_bucket(heads, M);

    int keys[N];
    generate(keys,N);
    printf("numbers:");
    print_array(keys, N);

    insert_bucket(heads, keys, N);
    printf("ordered:");
    print_keys(heads, M);
    printf("\n");
    return 0;
}