C语言基数排序算法实现

jack1007

这里的基数排序用LSD方法，即从最右边位开始，把位数相同的放在一起，这步需要把数组按这个规则分配到一个二维数组，分配完后，再把这个二维数组从新顺序放回到原来数组。
然后从右二位开始，重复以上，直到数组里面位数最高的数都分配过。最后放回原来数组的时候，整个数组就是顺序的了。还有就是要先知道数字位数的范围，这里最多为3位数。
整个算法很好理解，主要是程序里面的处理位数，复制数组很麻烦，不小心就错了。

1. #include <stdio.h>
   
2. 
   
3. void print_arr(int *arr, int arr_len);
   
4. void radixsort(int *arr, int base_bit, int arr_len);
   
5. long power_int(int base_n, int exp);
   
6. 
   
7. int
   
8. main()
   
9. {
   
10.   int arr[] = {512, 51, 13, 6, 61, 40, 72, 93, 49, 25, 201, 364};
    
11.   int base_bit = 3;
    
12.   int arr_len = sizeof(arr) / sizeof(arr[0]);
    
13.   print_arr(arr, arr_len);
    
14.   radixsort(arr, base_bit, arr_len);
    
15.   print_arr(arr, arr_len);
    
16.   return 0;
    
17. }
    
18. 
    
19. void
    
20. radixsort(int *arr, int base_bit, int arr_len)
    
21. {
    
22.   int temp_arr[10][arr_len];
    
23.   long max_base;
    
24.   max_base = power_int(10, base_bit);
    
25.   int base = 1;
    
26.   int i, j;
    
27.   int bit;
    
28.   int count[10] = {0};
    
29.   int k = 0;
    
30.   while (base <= max_base) {
    
31.     for (i = 0; i < arr_len; i++) {
    
32.       bit = (arr[i] / base) % 10;
    
33.       temp_arr[bit][count[bit]] = arr[i];
    
34.       count[bit]++;
    
35.     }
    
36.     for (i = 0; i < 10; i++) {
    
37.       if (count[i] != 0) {
    
38.         for (j = 0; j < count[i]; j++) {
    
39.           arr[k] = temp_arr[i][j];
    
40.           k++;
    
41.         }
    
42.         count[i] = 0;
    
43.       }
    
44.     }
    
45.     base *= 10;
    
46.     k = 0;
    
47.   }
    
48. 
    
49. }
    
50. 
    
51. void
    
52. print_arr(int *arr, int arr_len)
    
53. {
    
54.   int i = 0;
    
55.   while (i < arr_len) {
    
56.     printf("%d ", arr[i]);
    
57.     i++;
    
58.   }
    
59.   printf("\n");
    
60. }
    
61. 
    
62. long
    
63. power_int(int base_n, int exp)
    
64. {
    
65.   int i;
    
66.   long result = 1;
    
67.   for (i = 1; i < exp; i++) {
    
68.     result *= base_n;
    
69.   }
    
70.   return result;
    
71. }

复制代码