如何将Radix Sort用于浮点数数组? [英] How can I use Radix Sort for an array of float numbers?
问题描述
如何使用Radix Sort对数组中的一些浮点数据进行排序?我认为我应该将所有数据乘以10的最小幂,从而使它们成为整数.但是我不知道如何理解这种合适的力量.这是用于对整数数组进行排序的c ++代码.有人可以帮我吗?
How can I sort some float data in an array , using Radix Sort? I think that I should multiply all data into the smallest power of 10 which makes them integer. But I don't know how I can understand that suitable power. This is the c++ code for sorting an array of integers. Can anybody help me doing this?
#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;
}
推荐答案
除特殊数字(如NAN)外,您可以将浮点数视为32位符号+大小数字以进行排序.对于基数排序,将符号+量级数字转换为32位无符号整数,然后在排序后转换回最简单.从float到unsigned以及从unsigned到float的示例宏.请注意,-0将被视为小于+0,但这不应该成为问题.使用这些宏之前,将浮点数强制转换为无符号的int.
Except for special numbers like NAN, you can treat floats as 32 bit sign + magnitude numbers for sorting purposes. For radix sorting, it would be simplest to convert sign + magnitude numbers to 32 bit unsigned integers, then convert back after the sort. Example macros to convert from float to unsigned and from unsigned to float. Note that -0 would be treated as less than +0, but this should not be an issue. Cast a float to an unsigned int before using these macros.
#define FLOAT_2_U(x) ((x)^(((~(x) >> 31)-1) | 0x80000000))
#define U_2_FLOAT(x) ((x)^((( (x) >> 31)-1) | 0x80000000))
这篇关于如何将Radix Sort用于浮点数数组?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!