数据结构排序-基数排序

浏览数：18 / 时间：2015年06月08日

基数排序是跟前面的几种排序算法完全不一样的排序算法，前面的排序算法主要通过关键字之间的比较和移动来实现，而基数排序不需要进行关键字之间的比较，它是借助多关键字的思想来实现的。对于数字，每一位上的数字就是一个关键字，每一位的数字范围就是关键字范围，它的主要过程为：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列，如下图所示。类似从低位到高位比较，就是从次关键字到主关键字比较，这种称为最低位优先（LSD），反之称为最高位优先（MSD）。时间复杂度为O（kn）。

技术分享

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 int n;    //元素个数
 5 int bit_num;    //最大数字位数
 6 
 7 /*
 8  * 获取相应位置上的数（从右到左）
 9  */
10 int GetNumInPos(int num, int pos)
11 {
12     int i, temp = 1;
13     for (i = 0; i < pos - 1; i++)
14     {
15         temp *= 10;
16     }
17     return (num / temp) % 10;
18 }
19 
20 /*
21  * 基数排序（LSD）
22  */
23 void RadixSort(int *array)
24 {
25     int radix = 10;
26     int *count, *bucket, i, j, k;
27     count = (int*) malloc(sizeof(int) * radix);
28     bucket = (int*) malloc(sizeof(int) * n);
29     for (k = 1; k <= bit_num; k++)
30     {
31         for (i = 0; i < radix; i++)
32         {
33             count[i] = 0;
34         }
35         //统计各个桶中所盛数据个数
36         for (i = 0; i < n; i++)
37         {
38             count[GetNumInPos(array[i], k)]++;
39         }
40         //count[i]表示第i个桶的右边界索引
41         for (i = 1; i < radix; i++)
42         {
43             count[i] = count[i] + count[i - 1];
44         }
45         //分配
46         for (i = n - 1; i >= 0; i--)
47         {
48             j = GetNumInPos(array[i], k);
49             bucket[count[j] - 1] = array[i];
50             count[j]--;
51         }
52         //收集
53         for (i = 0, j = 0; i < n; i++, j++)
54         {
55             array[i] = bucket[j];
56         }
57     }
58 }
59 
60 int main()
61 {
62     int i;
63     int *array;
64     printf("请输入最大数字的位数：");
65     scanf("%d", &bit_num);
66     printf("请输入数组的大小：");
67     scanf("%d", &n);
68     array = (int*) malloc(sizeof(int) * n);
69     printf("请输入数据（用空格分隔）：");
70     for (i = 0; i < n; i++)
71     {
72         scanf("%d", &array[i]);
73     }
74     RadixSort(array);
75     printf("排序后为：");
76     for (i = 0; i < n; i++)
77     {
78         printf("%d ", array[i]);
79     }
80     printf("\n");
81 }