如何优雅修改Java队列版基数排序以支持正浮点数排序？

方案一：通过精确缩放转换为整数排序（无需字符串操作） #

核心思路 #

直接转字符串提取小数位数不够优雅，且浮点数的二进制存储易引发精度误差（比如0.1作为double存储时并非精确值）。我们可以借助BigDecimal精准获取每个浮点数的小数位数，计算出最大缩放倍数，将所有正浮点数转换为无精度损失的整数后复用整数基数排序逻辑，排序完成后再转换回浮点数。

代码实现 #

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class RadixSort {
    // 适配long类型的整数基数排序（避免int溢出）
    private static void radixSortLong(long[] array) {
        if (array.length == 0) return;
        long max = getMaxElement(array);

        List<Queue<Long>> queues = new ArrayList<>(10);
        for (int i = 0; i < 10; i++) {
            queues.add(new LinkedList<>());
        }

        // 修正循环条件：直到最高位处理完毕
        for (long exp = 1; max / exp > 0; exp *= 10) {
            for (long value : array) {
                int digit = (int) ((value / exp) % 10);
                queues.get(digit).add(value);
            }

            // 出队回写原数组
            int index = 0;
            for (Queue<Long> queue : queues) {
                while (!queue.isEmpty()) {
                    array[index++] = queue.remove();
                }
            }
        }
    }

    // 正浮点数基数排序实现
    public static void radixSortPositiveDouble(double[] array) {
        if (array.length == 0) return;

        // 计算所有数中的最大小数位数
        int maxScale = 0;
        for (double num : array) {
            BigDecimal bd = new BigDecimal(Double.toString(num));
            maxScale = Math.max(maxScale, bd.scale());
        }

        long scale = (long) Math.pow(10, maxScale);
        long[] tempArray = new long[array.length];

        // 精确转换为整数
        for (int i = 0; i < array.length; i++) {
            BigDecimal bd = new BigDecimal(Double.toString(array[i]));
            tempArray[i] = bd.multiply(new BigDecimal(scale)).longValue();
        }

        // 对整数数组排序
        radixSortLong(tempArray);

        // 转换回浮点数
        for (int i = 0; i < array.length; i++) {
            array[i] = tempArray[i] / (double) scale;
        }
    }

    private static long getMaxElement(long[] array) {
        long max = array[0];
        for (long num : array) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }
}

方案二：直接处理浮点数的每一位（无需转换为整数） #

核心思路 #

基数排序的本质是按每一位数字分桶收集，针对浮点数我们可以拆分处理：

1. 先处理小数部分：从第1位小数开始，到最长的小数位结束
2. 再处理整数部分：从个位开始，到最大数的最高位结束

这种方式无需转换数据类型，避免了大数溢出风险。

代码实现 #

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class RadixSort {
    public static void radixSortPositiveDouble(double[] array) {
        if (array.length == 0) return;

        // 步骤1：处理小数部分
        int maxDecimalDigits = getMaxDecimalDigits(array);
        for (int d = 1; d <= maxDecimalDigits; d++) {
            List<Queue<Double>> queues = new ArrayList<>(10);
            for (int i = 0; i < 10; i++) {
                queues.add(new LinkedList<>());
            }

            // 按当前小数位分桶
            for (double num : array) {
                double scaled = num * Math.pow(10, d);
                int digit = (int) (scaled % 10);
                queues.get(digit).add(num);
            }

            // 收集回原数组
            int index = 0;
            for (Queue<Double> queue : queues) {
                while (!queue.isEmpty()) {
                    array[index++] = queue.remove();
                }
            }
        }

        // 步骤2：处理整数部分
        double max = getMaxElement(array);
        for (long exp = 1; max / exp >= 1; exp *= 10) {
            List<Queue<Double>> queues = new ArrayList<>(10);
            for (int i = 0; i < 10; i++) {
                queues.add(new LinkedList<>());
            }

            // 按当前整数位分桶
            for (double num : array) {
                int digit = (int) ((num / exp) % 10);
                queues.get(digit).add(num);
            }

            // 收集回原数组
            int index = 0;
            for (Queue<Double> queue : queues) {
                while (!queue.isEmpty()) {
                    array[index++] = queue.remove();
                }
            }
        }
    }

    // 计算最长小数位数（用精度阈值避免浮点数误差）
    private static int getMaxDecimalDigits(double[] array) {
        int maxDigits = 0;
        for (double num : array) {
            double fractionalPart = num - Math.floor(num);
            if (fractionalPart == 0) continue;

            int count = 0;
            // 循环乘以10，直到小数部分趋近于0
            while (Math.abs(fractionalPart - Math.floor(fractionalPart)) > 1e-10) {
                fractionalPart *= 10;
                count++;
                fractionalPart = fractionalPart - Math.floor(fractionalPart);
            }
            maxDigits = Math.max(maxDigits, count);
        }
        return maxDigits;
    }

    private static double getMaxElement(double[] array) {
        double max = array[0];
        for (double num : array) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }
}

方案对比 #

• 方案一：逻辑简洁，复用整数排序代码，适合小数位数不多的场景；借助BigDecimal避免了浮点数转整数的精度问题。
• 方案二：无需数据类型转换，直接操作浮点数的每一位，避免了大数溢出风险，但代码逻辑稍复杂，需要分别处理小数和整数部分。

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