基数排序(Radix sort)是一种非比较型整数排序算法。
1. 基本思想
原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。
- MSD:先从高位开始进行排序,在每个关键字上,可采用计数排序
- LSD:先从低位开始进行排序,在每个关键字上,可采用桶排序
2. 实现逻辑
① 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。
② 从最低位开始,依次进行一次排序。
③ 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
分步图示说明:设有数组 array = {53, 3, 542, 748, 14, 214, 154, 63, 616},对其进行基数排序:
在上图中,首先将所有待比较数字统一为统一位数长度,接着从最低位开始,依次进行排序。
- 按照个位数进行排序。
- 按照十位数进行排序。
- 按照百位数进行排序。
排序后,数列就变成了一个有序序列。
5. 代码实现
int maxbit(int data[], int n) //辅助函数,求数据的最大位数 { int maxData = data[0]; ///< 最大数 /// 先求出最大数,再求其位数,这样有原先依次每个数判断其位数,稍微优化点。 for (int i = 1; i < n; ++i) { if (maxData < data[i]) maxData = data[i]; } int d = 1; int p = 10; while (maxData >= p) { //p *= 10; // Maybe overflow maxData /= 10; ++d; } return d; /* int d = 1; //保存最大的位数 int p = 10; for(int i = 0; i < n; ++i) { while(data[i] >= p) { p *= 10; ++d; } } return d;*/ } void radixsort(int data[], int n) //基数排序 { int d = maxbit(data, n); int *tmp = new int[n]; int *count = new int[10]; //计数器 int i, j, k; int radix = 1; for(i = 1; i <= d; i++) //进行d次排序 { for(j = 0; j < 10; j++) count[j] = 0; //每次分配前清空计数器 for(j = 0; j < n; j++) { k = (data[j] / radix) % 10; //统计每个桶中的记录数 count[k]++; } for(j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶 for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中 { k = (data[j] / radix) % 10; tmp[count[k] - 1] = data[j]; count[k]--; } for(j = 0; j < n; j++) //将临时数组的内容复制到data中 data[j] = tmp[j]; radix = radix * 10; } delete []tmp; delete []count; }