不基于比拟的排序，核心思想就是桶排序，工夫复杂度都是 O(N)，常见的不基于比拟的排序有 计数排序、基数排序。

一、计数排序

实用于排序元素的值 范畴比拟小的，且是整数。（例如：年龄）

1、外围思路：

（1）先筹备一个无限个数（比方 200）的整型辅助数组，挨个遍历原始数组，失去的值是 i，则将辅助数组 i 地位的值加一

（2）遍历辅助数组，如果数组地位 i 上的值是 k，则输入 k 个 i，失去的即是排好序的数组

2、具体参考代码：

/**
 * @author Java 和算法学习：周一
 */
public static void countSort(int[] arr) {if (arr == null || arr.length < 2) {return;}

    // 统计
    int max = Integer.MIN_VALUE;
    for (int v : arr) {max = Math.max(max, v);
    }
    int[] bucket = new int[max + 1];
    for (int v : arr) {bucket[v]++;
    }

    // 排序
    int i = 0;
    for (int j = 0; j < bucket.length; j++) {while (bucket[j]-- > 0) {arr[i++] = j;
        }
    }
}

从第一步中就能看进去，如果排序的值跨度比拟大，那么得筹备一个很大的辅助数组，然而数组绝大部分都是空着的，所以极大的节约空间，由此也能看出计数排序的局限性。

二、基数排序

实用于十进制正整数。

1、外围思路：

（1）遍历整个数组，失去最大值的十进制位数，同时将不满足最大位数的数高位补 0

（2）筹备十个桶，从 0 – 9 编号，每个桶大小为原数组大小

（3）遍历数组，以个位数为规范，个位数的值是 i，则将其放到第 i 号桶里；遍历完后，从 0 号桶开始，挨个将外面的数倒进去（先进先出）。此时的数是依据个位数排序

（4）遍历数组，以十位数为规范，十位数的值是 i，则将其放到第 i 号桶里；遍历完后，从 0 号桶开始，挨个将外面的数倒进去（先进先出）。此时的数是依据十位数排序

……直到遍历到最高位，最初倒进去的数即已排好序。

理论代码编写的时候，并没有筹备十个桶，而是筹备的一个长度为 10 的数组，这样能够大大节俭空间。

2、具体参考代码：

/**
 * @author Java 和算法学习：周一
 */
public static void radixSort(int[] arr) {if (arr == null || arr.length < 2) {return;}
    sort(arr, 0, arr.length - 1, maxBit(arr));
}

/**
 * 查找数组最大十进制位数
 */
public static int maxBit(int[] arr) {
    int max = Integer.MIN_VALUE;
    for (int value : arr) {max = Math.max(max, value);
    }
    int res = 0;
    while (max != 0) {
        res++;
        max /= 10;
    }
    return res;
}

private static void sort(int[] arr, int l, int r, int digit) {
    int radix = 10;
    // 辅助数组
    int[] help = new int[r - l + 1];
    // 有多少位就进桶几次、出桶几次
    for (int d = 1; d <= digit; d++) {// 前缀和数组：count[i]以后位（d 位）是 [0-i] 的数有多少个
        int[] count = new int[radix];
        // 统计此时数组 d 位上的数各呈现了几次，for (int i = l; i <= r; i++) {// 失去 d 位上的值，范畴[0,9]
            int v = getDigit(arr[i], d);
            count[v]++;
        }
        // 此时，count[i]示意以后位（d 位）是 [0-i] 的数有多少个
        for (int i = 1; i < radix; i++) {count[i] = count[i] + count[i - 1];
        }
        // 从右到左出桶
        for (int i = r; i >= l; i--) {
            // 失去 d 位上的值
            int v = getDigit(arr[i], d);
            help[--count[v]] = arr[i];
        }
        // 拷贝回原数组
        for (int i = 0; i < help.length; i++) {arr[l + i] = help[i];
        }
    }
}

public static int getDigit(int x, int d) {return ((x / ((int) Math.pow(10, d - 1))) % 10);
}

三、基于比拟的排序和不基于比拟的排序比照

基于比拟的排序适用范围更广（任何状况都能够），但工夫复杂度极限是 O(N*logN)

不基于比拟的排序适用范围很窄，但工夫复杂度更好 O(N)

本文全副代码：https://github.com/monday-pro/algorithm-study/tree/master/src/basic/nocomparesort