计数排序（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;    }}

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的长度很大

最后：该思路适用于数组数量较少的计算 2 楼 tan4836128 2011-10-17 我得给楼主拍砖，算法展示出来，同时要分析说明思路，执行过程，优缺点分析，否则大家伙怎么看啊，尤其是新手，望楼主三思 3 楼 hongjn 2011-10-17 tan4836128 写道
缺点：该算法的的时间长度：data.length * （k+1），k为无限大的正整数，直接导致tmp的长度很大

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