对于比较排序，大家如果感兴趣，可以查看我的博客：http://10740184.blog.51cto.com/10730184/1774508


计数排序


思路：

我们假设升序排序
排序序列为2000，2001，3000，4000
遍历序列，取出最小值min，最大值max，开辟一个空间为max—min的空间大小的数组，遍历数组a将排序序列a中的每个元素出现的次数放在数组count的每个a[i]-min处。就是说，2000出现一次了，把次数1放在2000-2000位置处，2001出现的次数放在2001-2000位置上，3000出现的次数放在3000-2000位置上，4000出现的次数放在4000-2000位置上，5000出现的次数放在5000-2000位置上。后面遇到相同元素了，那将该位置处的次数加加就统计出每个元素的次数了。
这样，对于数组count，里面放的元素就是序列a的次数，count的下标就是a的元素。
往出来取元素的过程，就是拿出排序好的序列的过程。每次从数组count里拿出下标，放回去就可以了。如果此时count中的元素大于1，说明排序序列a有重复元素，那我们多拿几次就行了。


代码实现：

#define_CRT_SECURE_NO_WARNINGS1#include<iostream>usingnamespacestd;#include<assert.h>#include<vector>voidPrint(vector<int>a){for(inti=0;i<a.size();i++){cout<<a[i]<<"";}cout<<endl;}voidCountSort(vector<int>&a){intmax=a[0];intmin=a[0];//找出序列的最大值与最小值，开辟max-min+1个空间大小的count数组for(inti=1;i<a.size();i++){if(max<a[i])max=a[i];if(min>a[i])min=a[i];}int*count=newint[max-min+1];memset(count,0,(max-min+1)*sizeof(int));//将数组初始化/*对要排序的数组a进行个数统计，a数组的元素i就放在count数组的i-min处，而不是i处。因为：若序列为100020003000，开辟的count从下标0开始，就将1000放于count的1000-1000=0处*/for(inti=0;i<a.size();i++){count[a[i]-min]++;}//将count数组往回去拿，i+min代表还原下标intj=0;for(inti=0;i<max-min+1;i++){while(count[i]>0)//此时该数重复n次，那就将该数拿回去n次{a[j++]=i+min;count[i]--;}}}voidTestCountSort(){vector<int>a={12,34,12222,4568,26,1,16,10,2,4,4,93,7,5,2,4};CountSort(a);Print(a);}intmain(){TestCountSort();system("pause");return0;}



基数排序：

#define_CRT_SECURE_NO_WARNINGS1#include<iostream>usingnamespacestd;#include<assert.h>voidPrint(int*a,intsize){for(inti=0;i<size;i++){cout<<a[i]<<"";}cout<<endl;}intMaxRadix(int*a,intsize){intradix=10;intcount=1;inti=0;for(inti=0;i<size;i++){while(a[i]>radix){radix*=10;count++;}}returncount;}void_PartRadix(int*a,intsize,intdivisor){intcount[10]={0};//处理数组count，统计每个数据的个、十、百等位出现的个数for(inti=0;i<size;i++){intnum=a[i]/divisor;count[num%10]++;}//处理数组start，统计每个元素的起始位置intstart[10]={0};for(inti=1;i<10;i++){start[i]=start[i-1]+count[i-1];}//遍历数组a,将这些元素放在tmp的计算好的位置上int*tmp=newint[size];for(inti=0;i<size;i++){intnum=a[i]/divisor;tmp[start[num%10]++]=a[i];//若该位有重复数，则加加坐标向起始位置的后面放即可}//拷回个位或十位或百位排序好的数组，开始下一个位的排序for(inti=0;i<size;i++){a[i]=tmp[i];}}voidRadixSort(int*a,intsize){assert(a);for(inti=1;i<=MaxRadix(a,size);i++){intdivisor=1;//获得除数，便于依次得到数据个位、十位、百位……intk=i;while(--k){divisor*=10;}_PartRadix(a,size,divisor);}}voidTestRadixSort(){inta[]={12,34,12222,4568,26,1,16,10,2,4,4,93,7,5,2,4};RadixSort(a,sizeof(a)/sizeof(a[0]));Print(a,sizeof(a)/sizeof(a[0]));}intmain(){TestRadixSort();system("pause");return0;}