当前位置：编程文档 >> C/C++ >> 计数算法排序引发的问题
首页

计数算法排序引发的问题

所属类别：C/C++
文章作者：小小鸟
推荐指数：★★☆
文档人气：19
本周人气：3
发布日期：2008-8-14


假设对A[1...N]数组进行排序，用一个数组count[1...N]来统计每个数应该出现的位置，
Set count[1...N] = 0;
for i = N; i > 1; i--
for j = i-1; j >=1; j--;
if A[j] > A[i]
count[j]++;
else
count[i]++;
如对于数组 2 3 4 1 5
第一次count为：0 0 0 0 4
第二次count为：1 1 1 0 4
第三次count为：1 1 3 0 4
第四次count为：1 2 3 0 4
最后的count则对应了其出现的下标值
该算法优点是不需要移动记录



Distribution Counting
是对上面方法的改进，假设数组A的最大值和最小值分别为min max，设置一个count[min...max]数组来统计每个数应该出现的位置
Set count[min...max] = 0;
for( i = 1; i <= N; i++)
count[A[i] += 1;
for (i = min+1; i <= max; i++)
count[i] = count[i] + count[i-1];
该算法优点是不需要进行任何比较操作


 

文档说明：

     

相关文档


读取评论列表……