不基于比拟的排序，核心思想就是桶排序，工夫复杂度都是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