计数排序>
给定一组待排序的数据，找到这组数据中的最大值，然后开辟一个最大值加1的数组，用memset初始化为全0，然后再次遍历原数组，使得这个新开辟的数组中存储的是该数字出现的次数，此时只需要将新数组的内容写入原数组即可.
我们发现计数排序其实利用的是哈希的思想来统计次数,是一种非比较的排序,它的时间复杂度为O(N+范围),因为计数排序是一种以空间换取时间的排序算法.
计数排序的优化>
如果给定这样一组数据"1001,1002,1003",那仫按照之前的思路我们就需要开辟1004块空间，很明显存在极大的空间浪费.要优化它只能从减小开辟空间的个数入手了.
其实我们可以找出一组数据中的最大值和最小值，此时开辟的辅助数组只需要开辟max-min+1块即可，在统计次数要重新映射进辅助数组.
void CountSort(int *a,int size) { assert(a); int max=a[0]; int min=a[0]; //找到最大最小值 for (int i=0;i<size;++i) { if(a[i] > max) max=a[i]; if(a[i] < min) min=a[i]; } int range=max-min+1; int *tmp=new int[range]; memset(tmp,0,sizeof(int)*range); //统计数字出现的次数 for (int i=0;i<size;++i) { tmp[a[i]-min]++; } //还原初始数组 int index=0; for (int i=0;i<range;++i) { while (tmp[i]--) { a[index++]=i+min; } } delete[] tmp; }
基数排序>
基数排序是另一种非比较的排序，类似哈希桶.它的主要思想是:从低位开始将一组序列按照这一位值的大小放至相应的编号0~9中。等到低位排完之后再按照类似的想法继续排次低位，直至排到最高位为止，此时这个序列就是有序的序列.
int GetMaxDigit(int *a,int size) { //标识数量级 int base=10; //统计最大数据的位数 int digit=1; for (int i=0;i<size;++i) { while (a[i] >= base) { ++digit; base *= 10; } } return digit; } void LSDSort(int *a,int size) { assert(a); int base=1; int digit=GetMaxDigit(a,size); int *count=new int[10]; int *start=new int[10]; int *tmp=new int[size]; while(digit--) { //统计数字出现的次数 memset(count,0,sizeof(int)*size); for (int i=0;i<size;++i) { count[(a[i]/base)]++; } //求每组数据的起始位置 start[0]=0; for (int i=1;i<10;++i) { start[i]=start[i-1]+count[i-1]; } //将数据写入tmp中 for (int i=0;i<size;++i) { int num=(a[i]/base); tmp[start[num]]=a[i]; start[num]++; } //将tmp中的内容写入a中 for (int i=0;i<size;++i) { a[i]=tmp[i]; } base *= 10; } delete[] tmp; }
在上述找最大位的方法先设置数量级base=10,digit统计位数=1，遍历数组，如果存在大于等于数量级的数就更新数量级统计位数加1.当然这个方法不太好理解，另一种求位数的方法是:先遍历一遍数组找到数组中的最大值，求出最大值的位数.
基数排序的时间复杂度为O(N*digit),digit是这组待排序数据中的最大位，它的空间复杂度为O(N),基数排序是一种稳定的排序算法.
在这里就分享结束啦~~~
