一：计数排序
（1）当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。（2）算法的步骤如下：1.找出待排序的数组中最大和最小的元素2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）4.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
（3）代码
#include <ctime>#include <iostream>#include <cstdlib>#include <cstring>using namespace std;const int NUM_RANGE = 100;const int RATE = 10; // 进制// output the arrvoid print_arr(const int *arr,const int &n){int i;for(i=0; i<n; i++){if(!i){cout << arr[i];}else{cout << " " << arr[i];}}printf("\n");}// 计算最长的位数int counting_digits(int *arr,const int &n){int digits = 0;int MyMax = arr[0];int i;for(i=1; i!=n; ++i){if(MyMax < arr[i])MyMax = arr[i];}while(MyMax){++digits;MyMax /= RATE;}return digits;}// sort by counting 计数void counting_sort(int *ini_arr,int *sorted_arr,const int &n){//int digits = counting_digits(arr,n); // 用不到的int *count_arr = (int *)malloc(sizeof(int)*NUM_RANGE);// 相当于bitMap统计数量类似int i,j,k;memset(count_arr,0,sizeof(int)*NUM_RANGE);for(i=0; i!=n; ++i){//分别计数count_arr[ini_arr[i]]++;// 以实际的 元素值 为count_arr的下标}for(i=1; i!=NUM_RANGE; ++i){// 计算排序后的位置count_arr[i] += count_arr[i-1];}for(i=n-1;i>=0;–i){int index = count_arr[ini_arr[i]]-1;//排序后的下标sorted_arr[index] = ini_arr[i];count_arr[ini_arr[i]]–;// 这是为了处理重复的数据}free(count_arr);}int main(int argc, char *argv[]){int n;if(argc < 2){n = 10;}else{n = atoi(argv[1]);}int i;int *arr = (int *)malloc(sizeof(int)*n);int *sorted_arr = (int *)malloc(sizeof(int)*n);srand(time(0));for(i=0; i<n; i++){arr[i] = rand() % NUM_RANGE;}printf("ini_array: ");print_arr(arr, n);counting_sort(arr, sorted_arr, n);printf("sorted_array: ");print_arr(sorted_arr, n);free(arr);free(sorted_arr);return 0;}
二：基数排序
(1) 基数排序上面的问题是多关键字的排序，但单关键字也仍然可以使用这种方式。比如字符串“abcd” “aesc” "dwsc" "rews"就可以把每个字符看成一个关键字。另外还有整数 425、321、235、432也可以每个位上的数字为一个关键字。基数排序的思想就是将待排数据中的每组关键字依次进行桶分配。比如下面的待排序列：278、109、063、930、589、184、505、269、008、083我们将每个数值的个位，十位，百位分成三个关键字： 278 -> k1(个位)=8 ，k2(十位)=7 ，k3=(百位)=2。然后从最低位个位开始(从最次关键字开始)，对所有数据的k1关键字进行桶分配(因为，每个数字都是 0-9的，因此桶大小为10)，再依次输出桶中的数据得到下面的序列。930、063、083、184、505、278、008、109、589、269再对上面的序列接着进行针对k2的桶分配，输出序列为：505、008、109、930、063、269、278、083、184、589最后针对k3的桶分配，输出序列为：008、063、083、109、184、269、278、505、589、930(2) 性能分析很明显，基数排序的性能比桶排序要略差。每一次关键字的桶分配都需要O(N)的时间复杂度，而且分配之后得到新的关键字序列又需要O(N)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2N) ，当然d要远远小于N，因此基本上还是线性级别的。基数排序的空间复杂度为O(N+M)，其中M为桶的数量。一般来说N>>M，因此额外空间需要大概N个左右。但是，对比桶排序，基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作，而桶排序在桶相对较少的情况下，桶内多个数据必须进行基于比较操作的排序。因此，在实际应用中，基数排序的应用范围更加广泛。
（3）代码
#include <ctime>#include <iostream>#include <cstdlib>#include <cstring>using namespace std;const int NUM_RANGE = 100;const int RATE = 10; // 进制// output the arrvoid print_arr(const int *arr,const int &n){int i;for(i=0; i<n; i++){if(!i){cout << arr[i];}else{cout << " " << arr[i];}}printf("\n");}// 计算最长的位数int counting_digits(int *arr,const int &n){int digits = 0;int MyMax = arr[0];int i;for(i=1; i!=n; ++i){if(MyMax < arr[i])MyMax = arr[i];}while(MyMax){++digits;MyMax /= RATE;}return digits;}// sort by counting 计数void radix_sort(int *ini_arr,const int &n){int digits = counting_digits(ini_arr,n); int *cnt = (int *)malloc(sizeof(int)*RATE);// 0-9基数的个数啦，进制数int *sorted_arr = (int *)malloc(sizeof(int)*n);int i,j;int divide = 1;for(i=0;i!=digits;++i){memset(cnt,0,sizeof(int)*RATE);for(j=0;j!=n;++j){// 统计计数sorted_arr[j] = ini_arr[j];int index = (sorted_arr[j]/divide)%RATE;//取某一位作为下标cnt[index]++;}for(j=1; j!=RATE; ++j){cnt[j] += cnt[j-1];// 计算新的排名后的下标}// 非常类似于计数排序，逆序排列for(j=n-1; j>=0; –j){int index = (sorted_arr[j]/divide)%RATE;//取某一位作为下标ini_arr[cnt[index]-1] = sorted_arr[j];cnt[index]–;// 处理重复数据}divide *= RATE;}free(sorted_arr);free(cnt);}int main(int argc, char *argv[]){int n;if(argc < 2){n = 10;}else{n = atoi(argv[1]);}int i;int *arr = (int *)malloc(sizeof(int)*n);srand(time(0));for(i=0; i<n; i++){arr[i] = rand() % NUM_RANGE;}printf("ini_array: ");print_arr(arr, n);radix_sort(arr, n);printf("sorted_array: ");print_arr(arr, n);free(arr);return 0;}
三：桶排序
在时间里面我们什么也不能留下，包括痛苦，快乐和生命。
