基数排序c++实现

基数排序：是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。但在大部分的情况下还是在用在证书的情况下比较多。我这里也是只用了整数来实现。如果有负数，则可以用将负数序列反序的方法达到排序效果。如果是小数或字符串，那就将字符串拆下进行排序就可以了。

下面我来说说正整数用基数排序的原理：

假设有序列：23， 45， 21， 1， 321， 34， 0.我们要对其排序，首先将序列变成位数相同，位数不够的在前面补0,变成如下：

023

045

021

001

321

034

000

首先我们取最低位开始排，原因是如果要从高位排序, 那么次高位的排序会影响高位已经排好的大小关系. 因为高位的排序结果对数的影响是比较大的。如20和13，高位排的结果是20>13，而低位排的结果是13>20.

排一次的结果：

000

021

001

321

023

034

045

排第二次的结果：

000

001

021

321

023

034

045

排第三次的结果：

000

001

021

023

034

045

321

于是就得到了一个有序数列0，1，21，23，34，45，321 。

还有一点要说明的是，这里我们在对各位进行排序的时候要选择稳定排序，就是不能改变位值相同的数之间的相对位置，因为高位相同的时候大小是由低位决定的。所以稳定排序可以不影响这些数的相对位置。这里我用的是计数排序。在上篇讲计数排序那里我就说过，计数排序最大用处可能也就在这了。因为位数都是0~9，计数排序又足够快。空间上也不会很大开销。

下面是我的程序实现：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <vector>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 
 8 void radixSort(int* arrayL, int digit, int len) {
 9     int digitValue;
10     for (int i = 1; i <= digit; i++) {
11         vector<int> digitValueList[10];
12 
13         for (int j = 0; j != len; j++) {
14             //得到位值，相同位值得就加在后面，这样还是有序的。
15             digitValue = (arrayL[j] % (int)(pow(10.0, i)) - arrayL[j] % 
16                                        (int)(pow(10.0, i - 1))) / pow(10.0, i - 1);
17             digitValueList[digitValue].push_back(arrayL[j]); 
18         }
19         //把所有的元素读进数组
20         int count = 0;
21         for (int j = 0; j != 10; j++) {
22             for (int k = 0; k != digitValueList[j].size(); k++) {
23                 arrayL[count] = digitValueList[j][k];
24                 count++;
25             }
26         }    
27     }
28 }
29 
30 void output(int* arrayL, int len) {
31     for (int i = 0; i != len; i++)
32         printf("%d ", arrayL[i]);
33 }
34 int main(int argc, char const *argv[])
35 {
36     int lenOfArray;
37     int *arrayL;
38     printf("Enter the len of the array: ");
39     scanf("%d", &lenOfArray);
40     arrayL = new int[lenOfArray];
41     printf("Enter the elemrnt of array to sort: ");
42     for (int i = 0; i != lenOfArray; i++)
43         scanf("%d", &arrayL[i]);
44     int digit;
45     printf("Enter the len of biggest's digit: ");
46     scanf("%d", &digit);
47     radixSort(arrayL, digit, lenOfArray);
48     output(arrayL, lenOfArray);
49 
50     delete []arrayL;
51     return 0;
52 }

View Code