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数组计算每个待排序的数在上图数组中的位置，上图的数组就相当于收集了