计数排序（Counting Sort） O(n+k)

k为申请数组大小

介绍

计数排序是非比较的排序算法，对待排序的数据范围要求比较高，也就是尽量待排序的数值为正整数，一种牺牲时间还空间的算法。基于非比较进行排序，所以计数排序没有稳定性的说话。

算法描述

• 根据待排序数据的大小，估算初始化数组的大小K，S
• 遍里待排序的数列，将该数值a在数组S中找到对应的index，S[a]++,S[a]的值就代表数值a的个数
• 遍历数组S，将数组S中值大于0的index，存到新的数组中，保存的个数为S[index]

动图展示

countingSort.gif

代码实现

public class CountingSort {

    public static void main(String[] args) {
        int[] arrays = new int[]{27, 6, 27, 42, 23, 15, 38, 50, 35, 14, 40, 28, 29};
        int[] res = countingSort(arrays);
        print(res);

    }

    private static int[] countingSort(int[] arr) {
        //假设待排序的数值范围[0-1023]
        int[] temp = new int[1024];
        int[] res = new int[arr.length];
        for (int value : arr) {
            temp[value]++;
        }
        int idx = 0;
        for (int i = 0; i < temp.length; i++) {
            int value = temp[i];
            while (value-- > 0) {
                res[idx++] = i;
            }
        }
        return res;
    }

    private static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }
}