排序補充（計數基數排序）

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數組計算每個待排序的數在上圖數組中的位置，上圖的數組就相當於收集了