基数排序

基数排序不同于其他的七种排序算法，它是基于一种分配法，而非比较。基数排序属于“分配式排序”（distribution sort），基数排序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。它的灵感来自于队列(Queue)，它最独特的地方在于利用了数字的有穷性(阿拉伯数字只有0到9的10个)。

原理示例

基数排序gif

复杂度分析

排序方法 时间复杂度 空间复杂度 稳定性 复杂性
平均情况 最坏情况 最好情况
基数排序 O(d*(n+r)) O(d*(n+r)) O(d*(n+r)) O(n+r) 稳定 较复杂

其中，d 为位数，r 为基数，n 为原数组个数。 在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d * (n + r))。

实现要点：

首先我们需要一个能够放下所有一位数的桶（bucket），还好阿拉伯数字只有10个，所以我们只需要10个bucket就可以搞定，但是在将所有元素放入bucket时肯定会出现多个元素放入一个bucket的情况，这时候就需要使用链表来解决了（也有使用二维数组的方式，但是空间需要n^2，当排序元素很多时肯定有点吃不消），同时为了方便往bucket中遍历元素以及添加元素，我们让bucket包含两个指针，一个指向bucket中第一个元素（head），另一个指向最后一个元素（tail），而bucket中每个元素都是一个Node，Node中包含一个排序序列中的值（val）以及一个指向下一个元素的指针（next）。
有了桶，下一步就是需要将所有数值从个位开始依次放入桶，然后再按顺序取出放回原数组了，这里有个地方需要注意下，就是如何循环到数组中所有元素的最高位就终止循环，这里有两个解决方法：
（1）首先遍历一遍数组，找到最大值，确定最高位
（2）一直循环直到所有元素的指定位数都是0为止最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。

最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。

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
testBS()
{
    int a[] = {2, 343, 342, 1, 123, 43, 4343, 433, 687, 654, 3};
    int *a_p = a;
    //计算数组长度
    int size = sizeof(a) / sizeof(int);
    //基数排序
    bucketSort3(a_p, size);
    //打印排序后结果
    int i;
    for(i = 0; i < size; i++)
    {
        printf("%d\n", a[i]);
    }
    int t;
    scanf("%d", t);
}
//基数排序
void bucketSort3(int *p, intn)
{
    //获取数组中的最大数
    int maxNum = findMaxNum(p, n);
    //获取最大数的位数，次数也是再分配的次数。
    int loopTimes = getLoopTimes(maxNum);
    int i;
    //对每一位进行桶分配
    for(i = 1; i <= loopTimes; i++)
    {
        sort2(p, n, i);
    }
}
//获取数字的位数
int getLoopTimes(intnum)
{
    int count = 1;
    int temp = num / 10;
    while(temp != 0)
    {
        count++;
        temp = temp / 10;
    }
    return count;
}
//查询数组中的最大数
int findMaxNum(int *p, intn)
{
    int i;
    int max = 0;
    for(i = 0; i < n; i++)
    {
        if(*(p + i) > max)
        {
            max = *(p + i);
        }
    }
    return max;
}
//将数字分配到各自的桶中，然后按照桶的顺序输出排序结果
voidsort2(int *p, intn, intloop)
{
    //建立一组桶此处的20是预设的根据实际数情况修改
    int buckets[10][20] = {};
    //求桶的index的除数
    //如798个位桶index=(798/1)%10=8
    //十位桶index=(798/10)%10=9
    //百位桶index=(798/100)%10=7
    //tempNum为上式中的1、10、100
    int tempNum = (int)pow(10, loop - 1);
    int i, j;
    for(i = 0; i < n; i++)
    {
        int row_index = (*(p + i) / tempNum) % 10;
        for(j = 0; j < 20; j++)
        {
            if(buckets[row_index][j] == NULL)
            {
                buckets[row_index][j] = *(p + i);
                break;
            }
        }
    }
    //将桶中的数，倒回到原有数组中
    int k = 0;
    for(i = 0; i < 10; i++)
    {
        for(j = 0; j < 20; j++)
        {
            if(buckets[i][j] != NULL)
            {
                *(p + k) = buckets[i][j];
                buckets[i][j] = NULL;
                k++;
            }
        }
    }
}