计数排序

大约在2012年，第一次接触计数排序，当时觉得并不好理解。因为这个知识点比较冷，所以很快就忘了。
今天看到了相关文章，复习了一遍。

public int[] countSort(final int[] arr) {
    if (arr == null || arr.length == 0) {
        return new int[0];
    }
    int min = arr[0];
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
        }
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    int len = max - min + 1;
    int[] countArr = new int[len];
    // 计数
    for (int i = 0; i < arr.length; i++) {
        int index = arr[i] - min;
        countArr[index]++;
    }
    int[] sortedArr = new int[arr.length];
    int index = 0;
    // 排序
    for (int i = 0; i < countArr.length; i++) {
        for (int j = 0; j < countArr[i]; j++) {
            sortedArr[index++] = min + i;
        }
    }
    return sortedArr;
}


public static void main(String[] args) {
    int[] array = new int[10];
    for (int i = 0; i < array.length; i++) {
        array[i] = 90 + ThreadLocalRandom.current().nextInt(10);
    }
    System.out.println(Arrays.toString(array));
    int[] sortedArray = new CountSort().countSort(array);
    System.out.println(Arrays.toString(sortedArray));
}

单元测试要考虑到边界情况和长度是1的数组。
如果原数组的长度是N，计数数组的长度是M，那么计数排序的时间复杂度是O(M+N)，空间复杂度是O(M）
为什么这种排序算法并不常见？因为它有较大的局限性：

1. 适用于集中的元素，如果元素跨度很大，会导致复杂度变大。
2. 只能对整数排序

感谢：计数排序