1 基数排序的特点是研究多个关键字key,且多个key之间有权重之分，

   或者可把单个key建模为含有多个key的排序

   而计数排序、桶排序始终只有个一个key，或者说围绕着一个比较规则

   Ex：比较年月日，先比较年份，如果相同，比较月份，如果还是相同，就比较日

2 根据首先选择有效位的不同，分为两种

   A. 先比较最高有效位，然后在比较次高位的有效位，以此类推进行比较MSD(Most Significant Dight)

　    假如有189,321,312,167 需要考虑高有效位相同的情况与不同的情况

       最高位不同：直接分出大小，并且需要记住312与321 > 比189,167大 

       最高位相同：比较十位，并且根据上述记录只比较312与321之间的十位数，否则排序是不稳定的

   B. 先比较最低有效位，然后在比较次低位的有效位，以此类推进行比较LSD(Least Significant Dight)

       无需考虑MSD排序遇到的问题，直接对每个位数排序即可

       注意：每次排序只针对当前位数（辅助排序函数必须是基于稳定的）

3 可以使用基数排序对一些位数有限的十进制数排序(十进制整数每位固定大小0~9)

4 基数排序时间代价 O(d(n+k))(前提是辅助函数为计数排序的情况下)

   d为关键值key的位数的个数，每位排序执行计数排序需要O(n+k)

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 using namespace std;  5   6 const int SIZE = 10;  //n的大小  7 const int K = 1000;   //允许的最大整数  8 enum numberBit  9 { 10     GeWei     = 1, 11     ShiWei    = 10, 12     BaiWei    = 100, 13     QianWei   = 1000, 14 }; 15 //获取当前位数，d表示位数 16 int GetData(const int data, int d) 17 { 18     int tmp = 0; 19     switch(d) 20     { 21     case GeWei: 22         { 23             tmp = data%10; 24         } 25         break; 26     case ShiWei: 27         { 28             tmp = data%100; 29             tmp = tmp/10; 30         } 31         break; 32     case BaiWei: 33         { 34             tmp = data%1000; 35             tmp = tmp/100; 36         } 37         break; 38     case QianWei: 39         { 40             tmp = data/1000; //允许最大值为1000 41         } 42         break; 43     default: 44         { 45             cout <<"wrong number, which big then k"; 46             return -1; 47         } 48         break; 49     } 50     return tmp; 51 } 52 //计数排序, d为当前位数 53 void CountingSort(int array[], int size, int d) 54 { 55     //建立辅助数组pCount大小固定为10(0~9)，用来存储统计的元素信息 56     int *pCount = new int[10];    57     memset(pCount, 0, (10)*sizeof(pCount[0])); 58       59     //建立辅助数组result存储结果 60     int *result = new int[size];  61     memset(result, 0, size*sizeof(result[0])); 62  63     //数组p使用元素大小做为下标，统计array的每个元素的个数 64     for(int i=0; i<10; ++i) 65     { 66         int position = GetData(array[i], d);  //获取元素的位置 67         pCount[position] = pCount[position] + 1; 68     } 69  70     //数组p 记录每个元素x在数组array中 小于或等于x的个数  71     //比如个位数时：小于等于4 的为元素 为3个（0， 1000， 83）  72     for (int i=1; i<=9; ++i) 73     { 74         pCount[i] = pCount[i]+pCount[i-1]; 75     } 76  77     //根据上述获取的信息，进行排序 78     //比如个位数时：小于等于4的为元素为3个（0， 1000， 83），4的位置为第4个  79     for (int i=size-1; i>=0; --i)//此处为保证稳定性，从size-1 向 0 迭代  80     { 81         int data = GetData(array[i], d); 82         int position = pCount[data];      //获取数组array[i]的位置 83         result[position-1] = array[i];    //放到正确的位置 84         pCount[data]= pCount[data] - 1;   //更新该元素的个数 85     } 86     //把结果存储到最初的数组array 87     for (int i=0; i
        
         106     _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);107 108     int array[SIZE] = {
   328, 4, 456, 656, 0, 1000, 439, 725, 328, 83,};109 110     RadixSort(array, SIZE, K);111 112     for (int i=0; i
        
       
      
     

 

（转载请注明作者和出处^_*  Seven++   ）