介紹: 該算法不基于比較進(jìn)行排序，時(shí)間復(fù)雜度O(n + k)，很難說(shuō)與基于比較的排序算法（時(shí)間復(fù)雜度下限O(nlogn)）哪個(gè)更優(yōu)，具體要比較k與nlogn的大?。?/p>

實(shí)現(xiàn)思路:
1.以數(shù)組originArr中最大值max構(gòu)建一個(gè)長(zhǎng)度為max+1的數(shù)組countArr，以originArr中的元素為countArr數(shù)組的索引（index），以該元素在originArr數(shù)組中出現(xiàn)的次數(shù)為countArr數(shù)組index對(duì)應(yīng)的value；
2.構(gòu)建一個(gè)長(zhǎng)度為originArr.length的數(shù)組resultArr來(lái)保存排好序的元素；
3.遍歷countArr數(shù)組，找到countArr[index]的元素，一次將他們添加到resultArr中，如果countArr[index]大于0，例如countArr[index]==3，那么想resultArr添加index（也即是originArr的元素）3次；

代碼實(shí)現(xiàn)：

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;
    }