1 /**
  2  * 基數(shù)排序：C 語言
  3  *
  4  * @author skywang
  5  * @date 2014/03/15
  6  */
  7 
  8 #include <stdio.h>
  9 
 10 // 數(shù)組長度
 11 #define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )
 12 
 13 /*
 14  * 獲取數(shù)組a中最大值
 15  *
 16  * 參數(shù)說明：
 17  *     a -- 數(shù)組
 18  *     n -- 數(shù)組長度
 19  */
 20 int get_max(int a[], int n)
 21 {
 22     int i, max;
 23 
 24     max = a[0];
 25     for (i = 1; i < n; i++)
 26         if (a[i] > max)
 27             max = a[i];
 28     return max;
 29 }
 30 
 31 /*
 32  * 對數(shù)組按照"某個位數(shù)"進行排序(桶排序)
 33  *
 34  * 參數(shù)說明：
 35  *     a -- 數(shù)組
 36  *     n -- 數(shù)組長度
 37  *     exp -- 指數(shù)。對數(shù)組a按照該指數(shù)進行排序。
 38  *
 39  * 例如，對于數(shù)組a={50, 3, 542, 745, 2014, 154, 63, 616}；
 40  *    (01) 當(dāng)exp=1表示按照"個位"對數(shù)組a進行排序
 41  *    (02) 當(dāng)exp=10表示按照"十位"對數(shù)組a進行排序
 42  *    (03) 當(dāng)exp=100表示按照"百位"對數(shù)組a進行排序
 43  *    ...
 44  */
 45 void count_sort(int a[], int n, int exp)
 46 {
 47     int output[n];             // 存儲"被排序數(shù)據(jù)"的臨時數(shù)組
 48     int i, buckets[10] = {0};
 49 
 50     // 將數(shù)據(jù)出現(xiàn)的次數(shù)存儲在buckets[]中
 51     for (i = 0; i < n; i++)
 52         buckets[ (a[i]/exp)%10 ]++;
 53 
 54     // 更改buckets[i]。目的是讓更改后的buckets[i]的值，是該數(shù)據(jù)在output[]中的位置。
 55     for (i = 1; i < 10; i++)
 56         buckets[i] += buckets[i - 1];
 57 
 58     // 將數(shù)據(jù)存儲到臨時數(shù)組output[]中
 59     for (i = n - 1; i >= 0; i--)
 60     {
 61         output[buckets[ (a[i]/exp)%10 ] - 1] = a[i];
 62         buckets[ (a[i]/exp)%10 ]--;
 63     }
 64 
 65     // 將排序好的數(shù)據(jù)賦值給a[]
 66     for (i = 0; i < n; i++)
 67         a[i] = output[i];
 68 }
 69 
 70 /*
 71  * 基數(shù)排序
 72  *
 73  * 參數(shù)說明：
 74  *     a -- 數(shù)組
 75  *     n -- 數(shù)組長度
 76  */
 77 void radix_sort(int a[], int n)
 78 {
 79     int exp;    // 指數(shù)。當(dāng)對數(shù)組按各位進行排序時，exp=1；按十位進行排序時，exp=10；...
 80     int max = get_max(a, n);    // 數(shù)組a中的最大值
 81 
 82     // 從個位開始，對數(shù)組a按"指數(shù)"進行排序
 83     for (exp = 1; max/exp > 0; exp *= 10)
 84         count_sort(a, n, exp);
 85 }
 86 
 87 void main()
 88 {
 89     int i;
 90     int a[] = {53, 3, 542, 748, 14, 214, 154, 63, 616};
 91     int ilen = LENGTH(a);
 92 
 93     printf("before sort:");
 94     for (i=0; i<ilen; i++)
 95         printf("%d ", a[i]);
 96     printf("\n");
 97 
 98     radix_sort(a, ilen);
 99 
100     printf("after  sort:");
101     for (i=0; i<ilen; i++)
102         printf("%d ", a[i]);
103     printf("\n");
104 }

  1 /**
  2  * 基數(shù)排序：C++
  3  *
  4  * @author skywang
  5  * @date 2014/03/15
  6  */
  7 
  8 #include<iostream>
  9 using namespace std;
 10 
 11 /*
 12  * 獲取數(shù)組a中最大值
 13  *
 14  * 參數(shù)說明：
 15  *     a -- 數(shù)組
 16  *     n -- 數(shù)組長度
 17  */
 18 int getMax(int a[], int n)
 19 {
 20     int i, max;
 21 
 22     max = a[0];
 23     for (i = 1; i < n; i++)
 24         if (a[i] > max)
 25             max = a[i];
 26     return max;
 27 }
 28 
 29 /*
 30  * 對數(shù)組按照"某個位數(shù)"進行排序(桶排序)
 31  *
 32  * 參數(shù)說明：
 33  *     a -- 數(shù)組
 34  *     n -- 數(shù)組長度
 35  *     exp -- 指數(shù)。對數(shù)組a按照該指數(shù)進行排序。
 36  *
 37  * 例如，對于數(shù)組a={50, 3, 542, 745, 2014, 154, 63, 616}；
 38  *    (01) 當(dāng)exp=1表示按照"個位"對數(shù)組a進行排序
 39  *    (02) 當(dāng)exp=10表示按照"十位"對數(shù)組a進行排序
 40  *    (03) 當(dāng)exp=100表示按照"百位"對數(shù)組a進行排序
 41  *    ...
 42  */
 43 void countSort(int a[], int n, int exp)
 44 {
 45     int output[n];             // 存儲"被排序數(shù)據(jù)"的臨時數(shù)組
 46     int i, buckets[10] = {0};
 47 
 48     // 將數(shù)據(jù)出現(xiàn)的次數(shù)存儲在buckets[]中
 49     for (i = 0; i < n; i++)
 50         buckets[ (a[i]/exp)%10 ]++;
 51 
 52     // 更改buckets[i]。目的是讓更改后的buckets[i]的值，是該數(shù)據(jù)在output[]中的位置。
 53     for (i = 1; i < 10; i++)
 54         buckets[i] += buckets[i - 1];
 55 
 56     // 將數(shù)據(jù)存儲到臨時數(shù)組output[]中
 57     for (i = n - 1; i >= 0; i--)
 58     {
 59         output[buckets[ (a[i]/exp)%10 ] - 1] = a[i];
 60         buckets[ (a[i]/exp)%10 ]--;
 61     }
 62 
 63     // 將排序好的數(shù)據(jù)賦值給a[]
 64     for (i = 0; i < n; i++)
 65         a[i] = output[i];
 66 }
 67 
 68 /*
 69  * 基數(shù)排序
 70  *
 71  * 參數(shù)說明：
 72  *     a -- 數(shù)組
 73  *     n -- 數(shù)組長度
 74  */
 75 void radixSort(int a[], int n)
 76 {
 77     int exp;    // 指數(shù)。當(dāng)對數(shù)組按各位進行排序時，exp=1；按十位進行排序時，exp=10；...
 78     int max = getMax(a, n);    // 數(shù)組a中的最大值
 79 
 80     // 從個位開始，對數(shù)組a按"指數(shù)"進行排序
 81     for (exp = 1; max/exp > 0; exp *= 10)
 82         countSort(a, n, exp);
 83 }
 84 
 85 int main()
 86 {
 87     int i;
 88     int a[] = {53, 3, 542, 748, 14, 214, 154, 63, 616};
 89     int ilen = (sizeof(a)) / (sizeof(a[0]));
 90 
 91     cout << "before sort:";
 92     for (i=0; i<ilen; i++)
 93         cout << a[i] << " ";
 94     cout << endl;
 95 
 96     radixSort(a, ilen);    // 基數(shù)排序
 97 
 98     cout << "after  sort:";
 99     for (i=0; i<ilen; i++)
100         cout << a[i] << " ";
101     cout << endl;
102 
103     return 0;
104 }