十、基数排序

---

 

---

1.定义

(radix sort）则是属于”分配式排序”（distribution
sort），[基数排序法]{.ul}又称”桶子法”（bucket
sort）或bin
sort，顾名思义，它是透过键值的部份资讯，将要排序的[元素分配]{.ul}至某些”桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其[时间复杂度]{.ul}为O
(nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。

Pasted from:
<[http://baike.baidu.com/view/1170573.htm]{.ul}>

 

2.基本解法

第一步

以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相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个[数组]{.ul}中，而是在每个”桶子”中建立”子桶”，将每个桶子中的数值按照下一数位的值分配到”子桶”中。在进行完最低位数的分配后再合并回单一的[数组]{.ul}中。

3.实现方法

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

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

1. #include <stdlib.h>

2. #include <math.h>

3. testBS()

4. {

5. int a[] = {2,343,342,1,123,43,4343,433,687,654,3};

6. int *a_p = a;

7. //计算数组长度

8. int size = sizeof(a)/sizeof(int);

9. //基数排序

10. bucketSort3( a_p , size );

11. //打印排序后结果

12. int i ;

13. for(i = 0 ; i < size ; i++ ) {

14. printf(“%dn “,a[i]);

15. }

16. int t;

17. scanf(“%d”,t);

18. }

19. //基数排序

20. void bucketSort3(int *p , int n)

21. {

22. //获取数组中的最大数

23. int maxNum = findMaxNum( p , n );

24. //获取最大数的位数，次数也是再分配的次数。

25. int loopTimes = getLoopTimes(maxNum);

26. int i ;

27. //对每一位进行桶分配

28. for( i = 1 ; i <= loopTimes ; i++) {

29. sort2(p , n , i );

30. }

31. }

32. //获取数字的位数

33. int getLoopTimes(int num)

34. {

35. int count = 1 ;

36. int temp = num/10;

37. while( temp != 0 ) {

38. count++;

39. temp = temp / 10;

40. }

41. return count;

42. }

43. //查询数组中的最大数

44. int findMaxNum( int *p , int n)

45. {

46. int i ;

47. int max = 0;

48. for( i = 0 ; i < n ; i++) {

49. if(*(p+i) > max) {

50. max = *(p+i);

51. }

52. }

53. return max;

54. }

55. //将数字分配到各自的桶中，然后按照桶的顺序输出排序结果

56. void sort2(int *p , int n , int loop)

57. {

58. //建立一组桶 此处的20是预设的 根据实际数情况修改

59. int buckets[10][20] = {} ;

60. //求桶的index的除数

61. //如798 个位桶index = ( 798 / 1 ) % 10 = 8

62. // 十位桶index = ( 798 / 10 ) % 10 = 9

63. // 百位桶index = ( 798 / 100 ) % 10 = 7

64. // tempNum 为上式中的1、10、100

65. int tempNum = (int) pow(10 , loop-1);

66. int i , j ;

67. for( i = 0 ; i < n ; i++ ) {

68. int row_index = (*(p+i) / tempNum) % 10;

69. for(j = 0 ; j < 20 ; j++) {

70. if(buckets[row_index][j] ==NULL) {

71. buckets[row_index ][j] = *(p+i) ;

72. break;

73. }

74. }

75. }

76. //将桶中的数，倒回到原有数组中

77. int k = 0 ;

78. for(i = 0 ; i < 10 ; i++) {

79. for(j = 0 ; j < 20 ; j++) {

80. if(buckets[i][j] != NULL) {

81. *(p + k ) = buckets[i][j] ;

82. buckets[i][j]=NULL;

83. k++;

84. }

85. }

86. }

87. }