浮点数的基数排序

Question

我想用基数对 C 中的浮点数进行排序。下面是我的代码。但是，我的输出不正确。例如，如果我运行带有 3.1、-5 和 1 的代码，我的排序值将打印为 3.000000、-5.000000 和 1.000000。

我知道从 float 到 int 到 float 的正确转换，我需要应用以下逻辑，但我不确定如何将其集成到 rfloat() 中，因为我尝试过但遇到了很多错误。

我怎样才能正确地将按位基数排序应用于浮点数？

float x = 3.1, *y; 
    int *a; 
    
    a = (int *)&x; 
    y = (float *)a; 

    printf("%f",*y);

#include <stdio.h>
#include <stdlib.h>

void rs(unsigned int *a, int c) {
    int i;
    int m = a[0];
    int bt = 0;
    unsigned int *b = malloc(0 * sizeof(int));

    for (i = 0; i < c; i++) {
        if (a[i] > m)
            m = a[i]; 
    }

    while((m>>bt) > 0){ 
        int buck[2] = { 0 };

        for (i = 0; i < c; i++) { 
            buck[(a[i]>>bt)&1]++;
        }

        for (i = 1; i < 2; i++) { 
            buck[i] += buck[i-1];
        }

        for (i = c-1; i >= 0; i--) { 
            b[--buck[(a[i]>>bt)&1]] = a[i]; 
        }

        for (i = 0; i < c; i++) {
            a[i] = b[i]; 
        }
        bt++;
    }
    free(b); 
}

void rfloat(float *arr, int c) {
    int d[c]; 
    int i; 
    
    for(i = 0; i < c; i++){
        d[i] = (int)arr[i];
    }
    
    rs(d, c);
    
    for(i = 0; i < c; i++){
        arr[i] = (float)d[i]; 
    }
    
}

int main() {
    int size;  
    int i; 
    float* arr = malloc(0* sizeof(float)); 
    
    printf("Size: "); 
    scanf("%d", &size); 
    
    for (int i = 0; i < size; i++){
        printf("Values: ");
        scanf("%f", &arr[i]); 
    }
    
    rfloat(arr, size); 
    
    printf("Sorted: ");
    for (i = 0; i < size; i++){
        printf("%f ", arr[i]);
    }
    free(arr); 
}

Answer 1

Positive 浮点数的排序顺序与将其位模式排序为无符号整数时的排序顺序相同。负浮点数不会，它们以反向顺序排序，而不是您对它们的位模式进行排序。此外，负数浮点数排序在正数之后，如果你要按它们的位模式排序，因为它们的最高位已设置。

那我们怎么办？我们做一个转换。如果设置了最高位（使负数在它们之间正确排序），我们将翻转所有其他位，并且我们总是翻转最高位（以使负数和正数正确排序）。然后排序后我们逆向变换。

不需要四舍五入！

void rfloat(float* arr, size_t size) {
    assert(sizeof(unsigned) == sizeof(float) && sizeof(float) == 4);
    unsigned* d = malloc(size * sizeof(unsigned));
    
    for (size_t i = 0; i < size; i++) {
        // Interpret float as 32-bit unsigned.
        d[i] = *(unsigned*) &(arr[i]);

        // Flip all except top if top bit is set.
        d[i] ^= (((unsigned) (((int) d[i]) >> 31)) >> 1);

        // Flip top bit.
        d[i] ^= (1u << 31);
    }
    
    rs(d, size);
    
    // Inverse transform.
    for (size_t i = 0; i < size; i++) {
        d[i] ^= (1u << 31);
        d[i] ^= (((unsigned) (((int) d[i]) >> 31)) >> 1);
        arr[i] = *(float*) &(d[i]);
    }
    
    free(d);
}

请注意，此后您的代码仍然无法正常工作。您的基数排序例程有问题。但这是另一个问题，如果你自己想不通的话。

浮点数的基数排序

Radix Sort for Floats

c

casting

bit-shift

radix-sort