基数排序浮点数

Question

我正在尝试使用基数对浮点数进行排序。我当前的算法适用于无符号。例如，如果我输入值 12、100、1，我的排序值是 1、12 和 100。但是，当我在调用基数排序后使用函数将浮点数转换回整数时，我的值保持未排序状态。它们在用户输入时打印。

我不确定如何修改我当前的函数以便能够使用基数对浮点数进行排序。

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, 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);
}

Answer 1

存在多个问题。

你在应该使用unsigned（值）或size_t（sizes/indices）的地方到处使用int。
您分配了 0 个字节。
(m >> bt) > 0 不能用作停止条件，未指定等于或大于宽度的移位位。
将数据类型转换为 unsigned 后，循环边界不再起作用。

我冒昧地修正了上面的问题并选择了一些更好的变量名：

#include <limits.h>

void rs(unsigned int *a, size_t c) {
    size_t i;
    unsigned bit = 0;
    unsigned *b = malloc(c * sizeof(unsigned));

    unsigned m = a[0]; // Max element.
    for (i = 0; i < c; i++) {
        if (a[i] > m) m = a[i]; 
    }

    while (bit < CHAR_BIT*sizeof(m) && (m >> bit)) { 
        size_t bucket_len[2] = { 0, 0 };
        for (i = 0; i < c; i++) bucket_len[(a[i] >> bit) & 1]++;

        size_t bucket_end[2] = {bucket_len[0], bucket_len[0] + bucket_len[1]};
        for (i = c; i-- > 0; ) {
            size_t j = --bucket_end[(a[i] >> bit) & 1];
            b[j] = a[i]; 
        }

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

基数排序浮点数

Radix Sort Float

c

floating-point

bit-shift

radix-sort