1//建立一个排序用的顺序表结构L
 2#define MAXSIZE 9
 3typedef struct SqList
 4{
 5    int r[MAXSIZE];
 6    int length;
 7}SqList;
 8/*排序的交换函数*/
 9void swap(SqList* L,int i,int j)
10{
11    int temp = L->r[i];
12    L->r[i] = L->r[j];
13    L->r[j] = temp;
14}

 1int maxbit(SqList *L, int n) //辅助函数，求数据的最大位数
 2{
 3    int maxData = L->r[0];           // 最大数
 4    /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
 5    for (int i = 1; i < n; ++i)
 6    {
 7        if (maxData < L->r[i])
 8            maxData = L->r[i];
 9    }
10    int d = 1;
11    int p = 10;
12    while (maxData >= p)
13    {
14        //p *= 10; // Maybe overflow
15        maxData /= 10;
16        ++d;
17    }
18    return d;
19}
20void RadixSort(SqList *L) //基数排序
21{
22    int n = L->length;
23    int d = maxbit(L, n);
24    int* tmp = new int[n];
25    int* count = new int[10]; //计数器
26    int i, j, k;
27    int radix = 1;
28    for (i = 1; i <= d; i++) //进行d次排序
29    {
30        //每次分配前清空计数器
31        for (j = 0; j < 10; j++)
32            count[j] = 0;
33        //统计每个桶中的记录数
34        for (j = 0; j < n; j++)
35        {
36            k = (L->r[j] / radix) % 10;
37            count[k]++;
38        }
39        //将tmp中的位置依次分配给每个桶,求前缀和
40        for (j = 1; j < 10; j++)
41            count[j] += count[j - 1];
42        //将所有桶中记录依次收集到tmp中
43        for (j = n - 1; j >= 0; j--)
44        {
45            k = (L->r[j] / radix) % 10;
46            tmp[count[k] - 1] = L->r[j];
47            count[k]--;
48        }
49        //将临时数组的内容复制到data中
50        for (j = 0; j < n; j++)
51            L->r[j] = tmp[j];
52        //位数加1
53        radix = radix * 10;
54    }
55    delete[]tmp;
56    delete[]count;
57}

 1public int[] RadixSort(int[] nums)
 2{
 3    if(null == nums || nums.length < 2)
 4    {
 5        return nums;
 6    }
 7    //找出最大数
 8    int max = nums[0];
 9    for(int i = 0; i < nums.length; i++)
10    {
11        max = Math.max(max, nums[i]);
12    }
13    //先算出最大数的位数，他决定了我们需要进行几轮排序
14    int maxDigit = 0;
15    while(max != 0)
16    {
17        max /= 10;
18        maxDigit++;
19    }
20    int mod = 10, div = 1;
21    //构建桶
22    ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
23    for(int i = 0; i < 10; i++)
24    {
25        bucketList.add(new ArrayList<Integer>());
26    }
27    //按照从右往左的顺序，一次将每一位都当做一次关键字，然后按照该关键字对数组排序，每一轮都基于上一轮排序的结果
28    for(int i = 0; i < nums.length; i++)
29    {
30        int num = (nums[j] % mod) / div;
31        bucketList.get(num).add(nums[j]);
32    }
33    //看看桶中数据的分布
34    for(int b = 0; b < bucketList.size(); b++)
35    {
36        System.out.println("第" + b + "个桶包含数据");
37        PrintArray.printObject(bucketList.get(b));
38    }
39    //桶中的数据回写原始数据，清楚桶，准备下一轮的排序
40    int index = 0;
41    for(int j = 0; j < bucketList.size(); j++)
42    {
43        for(int k = 0; k < bucketList.get(j).size(); k++)
44        {
45            nums[index++] = bucketList.get(j).get(k);
46        }
47        bucketList.get(j).clear();
48    }
49    return nums;
50}