懂得分配和收集，就懂得了基数排序。_分配与收集

对于我们而言，当我们在生活中听到“排序”这个词时，我们的大脑就会产生几个关键词：顺序，大小，比较。顺序是结果，大小是标准，比较是方法。逻辑严谨，思维敏捷。但，如果有人告诉你，可以无需比较，就可以得到一组序列正确的顺序。你或许表面上说：是什么方法 ？，但心中早就爆发了: what ? 这个小赤佬，搞不了疯掉了，快跑吧，以后可不能和他玩了，我的智商啊！

小编在之前听到上面的话时，自己的表情变得和上面的图片一样。要多难看，就有多难看。但小编说，真的可以不需要比较，就可以完成数据的排序。小伙伴们听到这里，恐怕

不要，我的亲们。咱们可以先往下看看，再决定呀！

如果，我给小伙伴们一组数据

我们都知道，咱们的数字都是由0-9的范围数字组成的。我先设计出来10个桶(这里运用了一些桶排序的知识，但不知道也不影响咱们的学习，如果想要学习，可以看小编的：桶：难道只有短板效应吗？)，下标为0-9

我们先根据数字中个位中的数字放在相应下标的桶中

我们按照0-9的桶的顺序，当一个桶中有多个数据时，先取出最早放的，形成的新的数据为

我们利用新的数据顺序，使用十位，继续操作，得到的数据为

我们利用新的数据顺序，使用百位，继续操作，得到的数据为

执行到这里时，数据变为有序了，我们发现，在执行的过程之中，我们没有进行过一次排序，就把数据变为有序了，这就是数据结构中的基数排序。基数排序的要点：将整数按位数切割成不同的数字，然后按每个位数分别比较。

具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

分配：就是咱们的每一放在桶中的过程

收集：就是咱们将桶中的元素拿出来

当我学会这种排序时，真的

真的是：三人行必有我师焉。

看一下代码实现

/*  
 * 获取数组a中最大值
 * 参数说明：
 *     a -- 数组
 *     n -- 数组长度
 */
int get_max(int a[], int n)
{
    int i, max;
    max = a[0];
    for (i = 1; i < n; i++)
        if (a[i] > max)
            max = a[i];
    return max;
}
/*
 * 对数组按照"某个位数"进行排序(桶排序)
 *
 * 参数说明：
 *     a -- 数组
 *     n -- 数组长度
 *     exp -- 指数。对数组a按照该指数进行排序。
 *
 * 例如，对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}；
 *    (01) 当exp=1表示按照"个位"对数组a进行排序
 *    (02) 当exp=10表示按照"十位"对数组a进行排序
 *    (03) 当exp=100表示按照"百位"对数组a进行排序
 *    ...
 */
void count_sort(int a[], int n, int exp)
{
    int output[n];  // 存储"被排序数据"的临时数组
    int i, buckets[10] = {0};
    // 将数据出现的次数存储在buckets[]中
    for (i = 0; i < n; i++)
        buckets[ (a[i]/exp)%10 ]++;
    // 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。
    for (i = 1; i < 10; i++)
        buckets[i] += buckets[i - 1];
    // 将数据存储到临时数组output[]中
    for (i = n - 1; i >= 0; i--)
    {
        output[buckets[ (a[i]/exp)%10 ] - 1] = a[i];
        buckets[ (a[i]/exp)%10 ]--;
    }
    // 将排序好的数据赋值给a[]
    for (i = 0; i < n; i++)
        a[i] = output[i];
}

/*
 * 基数排序
 * 参数说明：
 *     a -- 数组
 *     n -- 数组长度
 */
void radix_sort(int a[], int n)
{
    int exp;    // 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；...
    int max = get_max(a, n);    // 数组a中的最大值
    // 从个位开始，对数组a按"指数"进行排序
    for (exp = 1; max/exp > 0; exp *= 10)
        count_sort(a, n, exp);
}
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