java计数排序

介绍: 该算法不基于比较进行排序，时间复杂度O(n + k)，很难说与基于比较的排序算法（时间复杂度下限O(nlogn)）哪个更优，具体要比较k与nlogn的大小；

实现思路:
1.以数组originArr中最大值max构建一个长度为max+1的数组countArr，以originArr中的元素为countArr数组的索引（index），以该元素在originArr数组中出现的次数为countArr数组index对应的value；
2.构建一个长度为originArr.length的数组resultArr来保存排好序的元素；
3.遍历countArr数组，找到countArr[index]的元素，一次将他们添加到resultArr中，如果countArr[index]大于0，例如countArr[index]==3，那么想resultArr添加index（也即是originArr的元素）3次；

代码实现：

public static void main(String[] args) {
        int[] arr = initIntArr();
        int[] resultArr = countSort(arr);
        List<Integer> list = Lists.newArrayList();
        for (int i : resultArr) {
            list.add(i);
        }
        String str = list.stream().map(x -> x + "").collect(Collectors.joining(","));
        System.out.println(str);
    }

    public static int findMax(@NonNull int[] arr) {
        for (int i = 0; i < (arr.length - 1); i++) {
            int temp = arr[i + 1];
            if (arr[i] > arr[i + 1]) {
                arr[i + 1] = arr[i];
                arr[i] = temp;
            }
        }
        return arr[arr.length - 1];
    }

    public static int[] initIntArr() {
        int[] arr = {2,3,1,5,4,6,9,7,8,0,11,15,10};
        return arr;
    }

    public static int[] countSort(int[] arr) {
        int max = findMax(arr);
        int[] countArr = new int[max + 1];
        int[] resultArr = new int[arr.length];
        for (int i : arr) {
            ++countArr[i];
        }

        int i = 0, j = 0;
        while (i<countArr.length) {
            if (countArr[i] > 0) {
                for (int z = 0; z < countArr[i]; z++) {
                    resultArr[j++] = i;
                }
            }
            i++;
        }
        return resultArr;
    }