如何使用基数排序来计算浮点数的数组？

如何使用基数排序对数组中的某些浮点数据进行排序？我认为我应该把所有数据乘以10的最小幂，这使它们成为整数。但我不知道我怎么能理解这种合适的力量。这是用于排序整数数组的C++代码。有人可以帮我做这个吗？如何使用基数排序来计算浮点数的数组？

#include<iostream> 
using namespace std; 
//Get maximum value in arr[] 

    int findMax(int arr[], int n) 
{ 
    int max = arr[0]; 
    for (int i = 1; i < n; i++) 
     if (arr[i] > max) 
     max = arr[i]; 
    return max; 
} 

// A function to do counting sort of arr[] according to 
// the digit represented by exp. 

    void countSort(int arr[], int n, int exp) 
{ 
    int outputArr[n]; // output array 
    int i, count[10] = {0}; 

// Store count of occurrences in count[] 

    for (i = 0; i < n; i++) 
     count[ (arr[i]/exp)%10 ]++; 

// Change count[i] so that count[i] now contains actual 
// position of this digit in output[] 

    for (i = 1; i < 10; i++) 
     count[i] += count[i - 1]; 

// Build the output array 

    for (i = n - 1; i >= 0; i--) 
    { 
     outputArr[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
     count[ (arr[i]/exp)%10 ]--; 
    } 

// Copy the output array to arr[], so that arr[] now 
// contains sorted numbers according to current digit 

    for (i = 0; i < n; i++) 
     arr[i] = outputArr[i]; 
} 

// The main function to that sorts arr[] of size n using Radix Sort 

    void radixsort(int arr[], int n) 
    { 

     int max = findMax(arr, n); 

// Do counting sort for every digit. Note that instead 
// of passing digit number, exp is passed. exp is 10^i 
// where i is current digit number 

    for (int exp = 1; max/exp > 0; exp *= 10) 
    countSort(arr, n, exp); 
    } 

// A utility function to print an array 

    void print(int arr[], int n) 
    { 
     for (int i = 0; i < n; i++) 
     cout << arr[i] << " "; 
    } 

    int main() 
{ 
    int arr[] = {506,2,41,33,5,965,73}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    radixsort(arr, n); 
    print(arr, n); 
    return 0; 
}

来源

2017-02-17 Andromeda

除了像NAN这样的特殊数字，您可以将浮点数视为32位符号+幅度数字进行排序。对于基数排序，将符号+量值数字转换为32位无符号整数是最简单的，然后在排序后转换回来。示例宏从float转换为unsigned，从unsigned转换为float。请注意，-0会被视为小于+0，但这不应该成为问题。在使用这些宏之前将浮点数转换为unsigned int。

#define FLOAT_2_U(x) ((x)^(((~(x) >> 31)-1) | 0x80000000)) 
#define U_2_FLOAT(x) ((x)^((((x) >> 31)-1) | 0x80000000))

来源

2017-02-17 17:40:23 rcgldr

这是通用的，还是只为IEEE浮动？另外，NAN和其他特殊值会发生什么？最后，这是否正确地处理非规范化的数字？ –

@JimMischel - 此方法适用于IEEE浮点数，特别是符号和数量级的浮点数。非规范化数字应该可以正常工作。取决于指数值，特殊值将被排序到前面或后面。 – rcgldr

如何使用基数排序来计算浮点数的数组？

回答

相关问题