1.计数排序

顾名思义，是对待排序数组中的数据进行统计，然后根据统计的数据进行排序，例如：

待排序数组：

a[] = { 100, 123, 112, 123, 201, 123, 112, 156, 156, 178, 185, 156, 123, 112 }

首先取出数组中最大值与最小值（这个不用说了吧）

最大值：201 最小值：100

因此该数组的数值范围为 201 - 100 + 1 = 102

开辟一个大小为102的数组 count[102] 并将所有元素初始化为0

再次遍历数组，以 a[ i - 100 ] 作为数组count的下标，对该项进行加1

得到的count数组应该是（这里count元素为0的项就不出现了，太多了）

count[ 0 ] = 1

count[ 12 ] = 3

count[ 23 ] = 4

count[ 56 ] = 3

count[ 78 ] = 1

count[ 85 ] = 1

count[ 101 ] = 1

其余的元素都为0

此时遍历count数组，将每个元素对应写回a数组，此时数组a应该为

a = { 100,112,112,112,123,123,123,123,156,156,156,178,185,201 }

可以看到，数组a已经排好了序。

代码如下：

voidCountSort(int*a,size_tn)//计数排序{assert(a);intmin=a[0];intmax=a[0];for(inti=1;i<n;++i){if(a[i]>max)max=a[i];elseif(a[i]<min)min=a[i];}intcountNum=max-min+1;int*countArray=newint[countNum];memset(countArray,0,sizeof(int)*(countNum));for(inti=0;i<n;++i){++countArray[a[i]-min];}intindex=0;for(inti=0;i<countNum;++i)//写回数组{while(countArray[i]--){a[index++]=i+min;}}delete[]countArray;}

可以看到，计数排序有很大的局限性，它适合对数据范围相对比较集中的数据集合进行排序。

2.基数排序

我们通过一个例子来看基数排序是怎样进行排序的

设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}

我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以0~9来表示的。

所以我们不妨把0~9视为10个桶。

我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是0，将这个数存入编号为0的桶中。



分类后，我们在从各个桶中，将这些数按照从编号0到编号9的顺序依次将所有数取出来。

这时，得到的序列就是个位数上呈递增趋势的序列。

按照个位数排序：{50, 30, 0, 100, 11, 2, 123, 543, 187, 49}

接着按照十位进行如上排序（注意：没有十位的数按照十位为0处理）

按照十位数排序：{0, 100, 2, 11, 123, 30, 543, 49, 50, 187}

接着按照百位进行如上排序（注意：没有百位的数按照百位为0处理）

按照百位数排序：{0, 2, 11, 30, 49, 50, 100, 123, 187, 543}

排序完成

代码如下：

intGetMaxBit(int*a,size_tn)//获取数组中数字最多的位{assert(a);intBitNum=1;inttmpData=10;for(inti=0;i<n;++i){while(tmpData<=a[i]){++BitNum;tmpData*=10;}}returnBitNum;}voidRadixSort(int*a,size_tn)//基数排序{assert(a);intmaxBit=GetMaxBit(a,n);intdigit=1;int*tmp=newint[n];intcountBit[10];//计数intstartBit[10];//起始位置for(inti=1;i<=maxBit;++i){memset(countBit,0,sizeof(int)*10);for(inti=0;i<n;++i){intbit=(a[i]/digit)%10;//先各位，在十位百位……++countBit[bit];}memset(startBit,0,sizeof(int)*10);startBit[0]=0;for(inti=1;i<10;++i){startBit[i]=startBit[i-1]+countBit[i-1];}for(inti=0;i<n;++i)//存入临时数组{intindex=startBit[(a[i]/digit)%10]++;tmp[index]=a[i];}for(inti=0;i<n;++i)//写回原数组{a[i]=tmp[i];}digit*=10;}delete[]tmp;}