计数排序

计数排序的原理

设被排序的数组为A,排序后存储到B，C为临时数组。所谓计数，首先是通过一个数组C[i]计算大小等于i的元素个数，此过程只需要一次循环遍历就可以；在此基础上，计算小于或者等于i的元素个数，也是一重循环就完成。下一步是关键：逆序循环，从length[A]到1，将A[i]放到B中第C[A[i]]个位置上。原理是：C[A[i]]表示小于等于a[i]的元素个数，正好是A[i]排序后应该在的位置。而且从length[A]到1逆序循环，可以保证相同元素间的相对顺序不变，这也是计数排序稳定性的体现。在数组A有附件属性的时候，稳定性是非常重要的。

计数排序的前提及适用范围

A中的元素不能大于k,而且元素要作为数组的下标，所以元素应该为非负整数。而且如果A中有很大的元素，不能够分配足够大的空间。所以计数排序有很大局限性，其主要适用于元素个数多，但是普遍不太大而且总小于k的情况，这种情况下使用计数排序可以获得很高的效率。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

计数排序算法的步骤：

1.找出待排序的数组中最大和最小的元素

2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项

3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）

4.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

实现代码：

voidCountSort(int*a,intsize){intmin=a[0],max=a[0];inti=0;for(i=0;i<size;i++){if(min>a[i]){min=a[i];//找出数组中最小的数}if(max<a[i]){max=a[i];//找出数组中的最大数}}intrange=max-min+1;int*count=newint[range];//初始化数组//memset(count,0,sizeof(int)*range);for(i=0;i<range;i++){count[i]=0;}//把数组a中数变成数组count中的0，1，2....for(i=0;i<size;i++){//把数组count中对应位置制成数字，代表这个位置有几个相同的数//列如制成1，代表这个位置有一个数//列如制成2，代表这个位置有两个相同的数count[a[i]-min]++;}intj=0;//把count中的数还原回数组a中，它就排好序了for(i=0;i<range;i++){//重复了n次，就拿回去n次while(count[i]>0){a[j++]=i+min;count[i]--;}}delete[]count;}

基数排序

算法思想：

待排序数组[62,14,59,88,16]简单点五个数字

分配10个桶,桶编号为0-9,以个位数数字为桶编号依次入桶,变成下边这样

| 0 | 0 | 62 | 0 | 14 | 0 | 16 | 0 | 88 | 59 |

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |桶编号

将桶里的数字顺序取出来,

输出结果:[62,14,16,88,59]

再次入桶,不过这次以十位数的数字为准,进入相应的桶,变成下边这样:

由于前边做了个位数的排序,所以当十位数相等时,个位数字是由小到大的顺序入桶的,就是说,入完桶还是有序

| 0 | 14,16 | 0 | 0 | 0 | 59 | 62 | 0 | 88 | 0 |

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |桶编号


因为没有大过100的数字,没有百位数,所以到这排序完毕,顺序取出即可

最后输出结果:[14,16,59,62,88]

实现代码：

//获取最大位数staticintGetMaxRadix(int*a,intsize){intradix=10;intcount=1;for(inti=0;i<size;i++){//注意这里必须是">=",假如你的最大数是100，如果//没有“=”的话，你获取最大位就是两位while(a[i]>=radix){radix*=10;count++;}}returncount;}staticvoid_RadixSort(int*a,intsize,intdivisor,int*tmp){intcount[10]={0};intstart[10]={0};//如果你处理的是个位，count代表就是数据个位在//count对应位置出现的个数。十位，百位类似。for(inti=0;i<size;i++){intnum1=a[i]/divisor;count[num1%10]++;}//个位，十位，百位等出现的起始位置for(intj=1;j<10;j++){start[j]=start[j-1]+count[j-1];}//根据start，将a中的数据放在tmp中,已排好序for(intk=0;k<size;k++){intnum2=a[k]/divisor;tmp[start[num2%10]++]=a[k];}//把排好序的数据放回a中for(intn=0;n<size;n++){a[n]=tmp[n];}}voidRadixSort(int*arr,intsize){assert(arr);int*tmp=newint[size];intn=GetMaxRadix(arr,size);for(inti=1;i<=n;i++){intdivisor=1;intk=i;while(--k){divisor*=10;}_RadixSort(arr,size,divisor,tmp);}delete[]tmp;}