假设对A[1N]数组进行排序,用一个数组count[1N]来统计每个数应该出现的位置,
Set count[1N] = 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[minmax]数组来统计每个数应该出现的位置
Set count[minmax] = 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];
该算法优点是不需要进行任何比较操作