Counting Sort算法可以对十进制数值进行排序吗？

计数排序完全支持十进制数值的排序，适配场景和实现方式如下：

1 适配场景说明 #

• 对于十进制整数：是计数排序的原生适配场景，只要待排序的数值取值范围可控，时间复杂度可以达到O(n+k)（n为待排序元素数量，k为数值范围差），效率远高于冒泡、快排等比较类排序算法。
• 对于带小数的十进制数值：也可以通过转换实现排序，只需要先统计所有待排序数值的最大小数位数n，将所有数值统一乘以10^n转为整数，完成排序后再除以10^n还原为原始十进制数值即可。

2 使用注意事项 #

• 计数排序的使用前提是待排序数值的范围差不能过大，例如待排序数值范围是0~200，仅需要长度201的计数数组即可；如果数值范围差达到百万级以上，计数数组的内存开销会急剧升高，不再适合使用计数排序。
• Java中处理带小数的十进制数值时，如果使用float/double存在精度丢失风险，可以用BigDecimal类完成乘10的n次方、还原的操作，避免精度误差。

3 原理示意图 #

简单Java实现示例（十进制整数排序） #

public class CountingSort {
    public static void countingSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 找最大值和最小值
        int max = arr[0], min = arr[0];
        for (int num : arr) {
            if (num > max) max = num;
            if (num < min) min = num;
        }
        // 初始化计数数组
        int[] count = new int[max - min + 1];
        for (int num : arr) {
            count[num - min]++;
        }
        // 还原排序后的数组
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[index++] = i + min;
                count[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 3, 5, 18, 21, 7, 3};
        countingSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
        // 输出：3 3 5 7 12 18 21 
    }
}

内容的提问来源于stack exchange，提问作者Drechao