应用场景: 数据重复出现次数大 数据紧凑。
主导思想:
用原数组的最大值为长度申请一个数组初始化为零，遍历原数组，将原数组的每个值当做新数组的下标 里面值++ ;arrNew[arr[i]]++ 。
最后遍历新数组 将新数组的每个非零值 循环变成0，即将 有序的数 导回原数组
代码:
//计数排序 适用于数据比较密集 而且重复率比较大的 数组 void CountingSort(int arr[],int nLen) { //参数检查 if(arr==NULL || nLen<=0)return ; int Max=0; //找到原数组 最大 值 for(int i=0;i<nLen;i++) { if(arr[i]>Max) Max=arr[i]; //记录下最大值 } //申请一个新数组 int *temp=(int *)malloc(sizeof(int )*(Max+1)); //新数组赋空 memset(temp,0, sizeof(int )*(Max+1)); //给这个数组赋值 for(int i=0;i< nLen;i++) { temp[arr[i]]++; } //定义一个原数组的索引 int index=0; //从这个数组里面拿出来 非零值 给 原来的数组赋值 for(int i=0;i<=Max;i++) { while( temp[ i] ) { arr[index++]=i; temp[ i] --; } } }
后记:
计数排序的 局限性较大。但其中 用到的 思想可以拿来参考，也是其价值所在。即不去进行 比较，每个值对应数组下标。
原文：http://www.cnblogs.com/ming-rui/p/5330437.html