Java中正浮点数的LSD基数排序

xxls0lw8 于 2023-05-15 发布在 Java

关注(0)|答案(1)|浏览(101)

我正在使用队列实现基数排序。到目前为止，它可以对整数进行排序，但我想修改它，使其也能对正浮点数进行排序。

public static void radixSort(int[] array) {
    int max = getMaxElement(array);

    List<Queue<Integer>> queues = new ArrayList<>(10);

    for (int i = 0; i < 10; i++)
        queues.add(new LinkedList<>());

    /* insert into queues based on radix */
    for (int exp = 1; max / exp > 1; exp *= 10) {
        for (int value: array) {
            int digit = value / exp % 10;
            queues.get(digit).add(value);
        }
    } 

    /* dequeue into original array */
    int index = 0;
    for (int i = 0; i < 10; i++) {
        while (!queue.get(i).isEmpty())
            array[index++] = queues.get(i).remove();
    }
}

我试着找到最长的小数位，然后将数组中的每个元素乘以10的幂，这样浮点数就可以按整数排序。但是，我使用的方法需要将它们转换为字符串，以找到.最长的小数位。有没有更优雅的方法来排序浮点数？

Java

来源：https://stackoverflow.com/questions/76254453/lsd-radix-sort-in-java-for-positive-floating-points

1条答案

按热度按时间

a11xaf1n1#

浮点数可以在很大的范围内（它们可能非常接近零，也可能非常远离零），所以我不会使用这种方法。相反，您可以按符号，指数和尾数排序：
您可以尝试使用二进制表示法。您可以使用Double#doubleToRawLongBits或类似工具将浮点数转换为其二进制表示形式。
然后，您可以提取符号部分，指数和尾数：

double yourNumber=13.37;
long longRepresentation=Double.doubleToRawLongBits(yourNumber);
long sign=longRepresentation&0x8000000000000000L;
long exponent = longRepresentation&0x7ff0000000000000L;
long mantissa = longRepresentation&0x000fffffffffffffL;

注意，如果一个数字的long表示大于另一个数字，则对应的浮点数也是如此。
符号的位置与long值的位置相同。此外，指数（比尾数更有效）位于有效位置。
因为你可能不想一遍又一遍地调用Double#doubleToLongBits，你可能想先转换你的数据long s，然后对它们进行排序，最后再转换回来：

public static void radixSort(double[] array) {
    long[] longArray=new long[array.length];
    for(int i=0;i<array.length;i++){
        longArray[i]=Double.doubleToRawLongBits(array[i]);
    }
    radixSort(longArray);
    for(int i=0;i<array.length;i++){
        array[i]=Double.longBitsToDouble(longArray[i]);
    }
}

应该注意的是，由于long值的结构，对long值使用基数排序很可能效率不高。比较排序算法可能更有效。

赞(0）回复(0）举报 2023-05-15

我来回答

Java中正浮点数的LSD基数排序

1条答案

相关问题

热门标签

最新问答