如何使用基數排序來計算浮點數的數組？

如何使用基數排序對數組中的某些浮點數據進行排序？我認爲我應該把所有數據乘以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

如何使用基數排序來計算浮點數的數組？

回答

相關問題