1 void CountSort(int *a , size_t size) 2 { 3     int max = a[0], min = a[0]; 4     for (int i =1; i < size; ++i) 5     { 6         if (max < a[i]) 7         { 8             max = a[i]; 9         }10         if (min > a[i])11         {12             min = a[i];13         }14     }15     int index = 0;16     int *CountArray = new int[max - min + 1];17     memset(CountArray, 0, sizeof(int)*(max - min + 1));18     for (int i = 0; i < size; ++i)19     {20         CountArray[a[i] - min]++;21     }22     for (int i = 0; i < max - min + 1; ++i)23     {24         for (int j = 0; j < CountArray[i]; ++j)25         {26             a[index++] = i + min;27         }28     }29 }

所谓的基数排序原理就和哈希表极像，适合使用在待排序的数都处在一个比较小的范围内，开辟好一定的辅助空间，按照直接定址法，将辅助空间对应的位置的计数增加，最后排序的时候只要把之前建好的辅助数组遍历输出一遍就好了

 

1 int GetMaxDigit(int *a,size_t size) 2 { 3     int digit = 1; 4     int max = 10; 5     for (int i = 0; i < size; ++i) 6     { 7         while (a[i] >= max) 8         { 9             digit++;10             max *= 10;11         }12     }13     return digit;14 }15 16 //一共需要几个数组呢？一个count,一个start还有一个收集用的暂存数组？最后拷贝回去就可以了！17 void DigitSort(int *a, size_t size)18 {19     int MaxDigit = GetMaxDigit(a, size);20     int curDigit = 1;21     int digit = 0;22     int Count[10];23     int Start[10];24     int *Bucket = new int[size];25     while (digit < MaxDigit)26     {27         memset(Count, 0, sizeof(int) * 10);28         memset(Start, 0, sizeof(int) * 10);29         for (int i = 0; i < size; ++i)30         {31             int num = a[i] / curDigit % 10;32             Count[num]++;33         }34         Start[0] = 0;35         for (int i = 1; i < 10; ++i)36         {37             Start[i] = Start[i - 1] + Count[i - 1];38         }39         for (int i = 0; i < size; ++i)40         {41             int num = a[i] / curDigit % 10;42             Bucket[Start[num]++] = a[i];43         }44         memcpy(a, Bucket, sizeof(int)*size);45         digit++;46         curDigit *= 10;47     }48 }

 基数排序又被称为桶排序，这里的代码例子是完成一个几位数的排序，可以看成先根据个位的数大小进行一次排序（扔进各自数的桶里（桶当然是有序的（0-9嘛）））然后进行按序收集，然后根据十位数扔进桶里，直到最高位

这里我并未使用类似的链表结构，而是采用一个顺序表

不停地往后存，使用count辅助数组进行计数（对应的0-9有几个数）,使用start数组计算每个待排序的数在上图数组中的位置，上图的数组就相当于收集了