计数排序（CountingSort） Java实现

/**
 * 计数排序
 */
public class CountingSort {

    /**
     * 输入数组的元素都是介于0..k之间的
     * @param data 待排序数组
     * @param k 最大元素
     * @return 排序结果
     */
    public static int[] sort(int[] data, int k) {
        // 存放临时数据的数组tmp，初始元素都是0；k为数组中最大元素
        int[] tmp = new int[k + 1];

        // 计算数组中每个元素i出现的次数，存入数组tmp中的第i项，即原数组中的元素值为tmp数组中的下标
        for (int i = 0; i <= data.length - 1; i++) {
            tmp[data[i]]++;
        }

        // 计算数组中小于等于每个元素的个数,即从tmp中的第一个元素开始，每一项和前一项相加
        for (int j = 1; j <= k; j++) {
            tmp[j] = tmp[j] + tmp[j - 1];
        }

        // result数组用来来存放排序结果
        int[] result = new int[data.length];
        for (int i = data.length - 1; i >= 0; i--) {
            result[tmp[data[i]] - 1] = data[i];
            tmp[data[i]]--;
        }

        return result;
    }
}

评论

3 楼 hongjn 2011-10-17  

tan4836128 写道

缺点：该算法的的时间长度：data.length * （k+1），k为无限大的正整数，直接导致tmp的长度很大

多谢热心的朋友分析。另外，这算法的运行时间是Θ(n + k)

2 楼 tan4836128 2011-10-17  

我得给楼主拍砖，算法展示出来，同时要分析说明思路，执行过程，优缺点分析，否则大家伙怎么看啊，尤其是新手，望楼主三思

1 楼 tan4836128 2011-10-17  

测试

最大数K：10（大于6的数都行）
data：               2,3,1,2,3,2,1,2,3,4,5,5,6,5
第一次循环后tmp状态：0,2,4,3,1,3,1,0,0,0,0,
第二次循环后tmp状态：0,2,6,9,10,13,14,14,14,14,14,
result：             1,1,2,2,2,2,3,3,3,4,5,5,5,6,

分析

由于tmp修改了一次，第一次循环暂不用考虑，如下：
最大数K：10
data：  2,3,1,2,3,2,1,2,3,4,5,5,6,5
tmp：   0,2,6,9,10,13,14,14,14,14,14,
result：1,1,2,2,2,2,3,3,3,4,5,5,5,6,

利用：data.length = tmp最大值，tmp记录data各数值出现次数，并累加后重新对tmp赋值

data中的数值作为tmp中的数组下标，tmp中的值又作为result的数组下标，result每插入一个值，tmp中对应位置的值-1，直到排序完成

缺点：该算法的的时间长度：data.length * （k+1），k为无限大的正整数，直接导致tmp的长度很大

最后：该思路适用于数组数量较少的计算