排序补充（计数基数排序）

void CountSort（int *a , size_t size）
{
int max = a[0], min = a[0];
for （int i =1; i < size; ++i）
{
if （max < a[i]）
{
max = a[i];
}
if （min > a[i]）
{
min = a[i];
}
}
int index = 0;
int *CountArray = new int[max - min + 1];
memset（CountArray, 0, sizeof（int）*（max - min + 1））;
for （int i = 0; i < size; ++i）
{
CountArray[a[i] - min]++;
}
for （int i = 0; i < max - min + 1; ++i）
{
for （int j = 0; j < CountArray[i]; ++j）
{
a[index++] = i + min;
}
}
}所谓的基数排序原理就和哈希表极像，适合使用在待排序的数都处在一个比较小的范围内，开辟好一定的辅助空间，按照直接定址法，将辅助空间对应的位置的计数增加，最后排序的时候只要把之前建好的辅助数组遍历输出一遍就好了int GetMaxDigit（int *a,size_t size）
{
int digit = 1;
int max = 10;
for （int i = 0; i < size; ++i）
{
while （a[i] >= max）
{
digit++;
max *= 10;
}
}
return digit;
}//一共需要几个数组呢？一个count,一个start还有一个收集用的暂存数组？最后拷贝回去就可以了！
void DigitSort（int *a, size_t size）
{
int MaxDigit = GetMaxDigit（a, size）;
int curDigit = 1;
int digit = 0;
int Count[10];
int Start[10];
int *Bucket = new int[size];
while （digit < MaxDigit）
{
memset（Count, 0, sizeof（int） * 10）;
memset（Start, 0, sizeof（int） * 10）;
for （int i = 0; i < size; ++i）
{
int num = a[i] / curDigit % 10;
Count[num]++;
}
Start[0] = 0;
for （int i = 1; i < 10; ++i）
{
Start[i] = Start[i - 1] + Count[i - 1];
}
for （int i = 0; i < size; ++i）
{
int num = a[i] / curDigit % 10;
Bucket[Start[num]++] = a[i];
}
memcpy（a, Bucket, sizeof（int）*size）;
digit++;
curDigit *= 10;
}
}基数排序又被称为桶排序，这里的代码例子是完成一个几位数的排序，可以看成先根据个位的数大小进行一次排序（扔进各自数的桶里（桶当然是有序的（0-9嘛）））然后进行按序收集，然后根据十位数扔进桶里，直到最高位这里我并未使用类似的链表结构，而是采用一个顺序表不停地往后存，使用count辅助数组进行计数（对应的0-9有几个数）,使用start数组计算每个待排序的数在上图数组中的位置，上图的数组就相当于收集了本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-05/131647.htm