基数排序

基数排序

基本解法

第一步

以LSD为例，假设原来有一串数值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

0

1 81

2 22

3 73 93 43

4 14

5 55 65

6

7

8 28

9 39

第二步

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配，这次是根据十位数来分配：

0

1 14

2 22 28

3 39

4 43

5 55

6 65

7 73

8 81

9 93

第三步

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个 ​​数组​​​中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的 ​​数组​​中。

效率分析

[1]   ：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的 ​​时间复杂度​​​为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。 空间效率：需要2*radix个指向队列的辅助空间，以及用于 ​​静态链表​​​的n个 ​​指针​​。

实现方法

最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。

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

实现原理

基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

java实现代码：

public class RadixSort { // 获取x这个数的d位数上的数字 // 比如获取123的1位数，结果返回3 public int getDigit(int x, int d) { int a[] = { 1, 1, 10, 100 }; // 本实例中的最大数是百位数，所以只要到100就可以了 return ((x / a[d]) % 10); } public void radixSort(int[] list, int begin, int end, int digit) { final int radix = 10; // 基数 int i = 0, j = 0; int[] count = new int[radix]; // 存放各个桶的数据统计个数 int[] bucket = new int[end - begin + 1]; // 按照从低位到高位的顺序执行排序过程 for (int d = 1; d <= digit; d++) { // 置空各个桶的数据统计 for (i = 0; i < radix; i++) { count[i] = 0; } // 统计各个桶将要装入的数据个数 for (i = begin; i <= end; i++) { j = getDigit(list[i], d); count[j]++; } // count[i]表示第i个桶的右边界索引 for (i = 1; i < radix; i++) { count[i] = count[i] + count[i - 1]; } // 将数据依次装入桶中 // 这里要从右向左扫描，保证排序稳定性 for (i = end; i >= begin; i--) { j = getDigit(list[i], d); // 求出关键码的第k位的数字， 例如：576的第3位是5 bucket[count[j] - 1] = list[i]; //放入对应的桶中，count[j]-1是第j个桶的右边界索引 count[j]--; // 对应桶的装入数据索引减一 } // 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表 for (i = begin, j = 0; i <= end; i++, j++) { list[i] = bucket[j]; } } } public int[] sort(int[] list) { radixSort(list, 0, list.length - 1, 3); return list; } // 打印完整序列 public void printAll(int[] list) { for (int value : list) { System.out.print(value + "\t"); } System.out.println(); } public static void main(String[] args) { int[] array = { 50, 123, 543, 187, 49, 30, 0, 2, 11, 100 }; RadixSort radix = new RadixSort(); System.out.print("排序前:\t\t"); radix.printAll(array); radix.sort(array); System.out.print("排序后:\t\t"); radix.printAll(array); }}

C实现代码：

基数排序：首先分配10个桶，桶的编号为零到九。按照最低位的有效数字插入到相应的桶中。然后按照次低位插入到相应的桶中。

#include#include#includeusing namespace std;//获取最大位数int get_max_digit(int array[], int n){ int digit, max; digit = 0; max = array[0]; for (int i = 1; i < n; i++) { if (array[i] > max) max = array[i]; } while (max) { digit++; max /= 10; } return digit;}//基数排序void RadixSort(int array[], int n){ //创建临时数组 int *temp = new int[n]; //位数：决定了排序趟数 int digit = get_max_digit(array, n); //计数数组 int count[10]; //排序 int r, i, d; for (r = 1; r <= digit; r++) { //重置计数数组 memset(count, 0, 10 * sizeof(int)); //把数据存储到临时数组 memcpy(temp, array, n*sizeof(int)); d = i = 1; while (i < r) { i++; d *= 10; } for (i = 0; i < n; i++) count[(array[i] / d) % 10]++; for (i = 1; i < 10; i++) count[i] += count[i - 1]; //数据回放 for (i = n - 1; i >= 0; i--) array[--count[(temp[i] / d) % 10]] = temp[i]; }}void print(int array[], int n){ for (int i = 0; i < n; i++) cout << setw(6) << array[i]; cout << endl;}int main(){ cout << "******基数排序***by David***" << endl; int array[] = { 123, 234, 45, 111, 6, 128 }; int n = sizeof(array) / sizeof(int); cout << "原序列" << endl; print(array, n); cout << "基数排序" << endl; RadixSort(array, n); print(array, n); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。