基数排序得到正确的键对有符号整数进行排序
Radix sort get the right key to sort signed integers
我很难找到用于使用基数排序算法进行排序的正确值。
我已经正确地实施了它,但是我对底片有疑问。我试着用二进制来反转值。它对我有一点帮助,但底片是按升序排列的,而不是按降序排列的。最有趣的是,排序适用于浮点数和有符号整数。
这是我构建排序键的函数:
uint32_t SortKeyToU32(int Value)
{
uint32_t Result = (uint32_t)Value;
if(Result & 0x80000000)
{
Result = ~Result;
}
else
{
Result |= 0x80000000;
}
return Result;
}
这是我的排序函数:
void RadixSort(int** Array, int Size)
{
int* Dest = new int[Size];
int* Source = *Array;
memset(Dest, 0, Size*sizeof(int));
for(int Bit = 0;
Bit < 32;
Bit += 8)
{
uint32_t ArrayOfValues[256] = {};
for(int Index = 0;
Index < Size;
++Index)
{
uint32_t SortKey = SortKeyToU32(Source[Index]);
uint32_t Key = (SortKey >> Bit) & 0xFF;
++ArrayOfValues[Key];
}
int Sum = 0;
for (int Index = 0;
Index < ArraySize(ArrayOfValues);
++Index)
{
uint32_t Count = ArrayOfValues[Index];
ArrayOfValues[Index] = Sum;
Sum += Count;
}
for(int Index = 0;
Index < Size;
++Index)
{
uint32_t SortKey = SortKeyToU32(Source[Index]);
uint32_t Key = (SortKey >> Bit) & 0xFF;
Dest[ArrayOfValues[Key]++] = Source[Index];
}
int* Temp = Source;
Source = Dest;
Dest = Temp;
}
}
但是我该如何处理有符号整数的排序呢?对不起,如果它看起来很明显。谢谢
编辑。
这是示例数组输入:1, 6, 9, 2, 3, -4, -10, 8, -30, 4
输出:-4、-10、-30、1、2、3、4、6、8、9
您需要的排序键公式非常简单:
uint32_t SortKeyToU32(int32_t Value) {
return uint32_t(Value) + (1U << 31);
}
下面的原因。首先,我们从 32 位有符号转换为无符号。此转换只是将有符号值的位重新解释为无符号值。
让我们看看有符号值是如何在数字的值 space 中显示的。为简单起见,让我们看一下 4 位有符号数,它总共有 16 个不同的值映射如下:
签署表格:
0, 1, 2, 3, 4, 5, 6, 7, -8, -7, -6, -5, -4, -3, -2, -1
未签名的形式:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
在有符号的情况下,前半部分值是 non-negative 升序排列,后半部分也是负值也是升序排列。
为了排序,我们需要所有负值排在正值之前,并且也按升序排列。对于上面的有符号 4 位值(无符号形式),我们只需要添加 8
,这恰好是范围的中间。因此,整个范围将随着溢出向右移动,负值将出现在正数之前(第一个数字下方是添加 8
后的数字,第二个数字(括号中)是原始数字(添加前)):
0 (-8), 1 (-7), 2 (-6), 3 (-5), 4 (-4), 5 (-3), 6 (-2), 7 (-1), 8 (0), 9 (1), 10 (2), 11 (3), 12 (4), 13 (5), 14 (6), 15 (7)
这正是我在排序键公式中所做的
uint32_t(Value) + (1U << 31)
我 reinterpret-casted 签署了无符号形式并添加了 middle-range 值,即 (1U << 31)
.
使用这个更正后的公式,您的代码可以正常工作,在下面的代码片段中,我也将您的原始排序键公式保留在名称 SortKeyToU32Old()
下,您可以更改排序键函数的名称以查看它之前的工作方式(错误地)并在(正确地)更改我的示例数组之后。
#include <cstdint>
#include <cstring>
#define ArraySize(a) (sizeof(a) / sizeof(a[0]))
uint32_t SortKeyToU32(int32_t Value) {
return uint32_t(Value) + (1U << 31);
}
uint32_t SortKeyToU32Old(int Value)
{
uint32_t Result = (uint32_t)Value;
if(Result & 0x80000000)
{
Result = ~Result;
}
else
{
Result |= 0x80000000;
}
return Result;
}
void RadixSort(int** Array, int Size)
{
int* Dest = new int[Size];
int* Source = *Array;
memset(Dest, 0, Size*sizeof(int));
for(int Bit = 0;
Bit < 32;
Bit += 8)
{
uint32_t ArrayOfValues[256] = {};
for(int Index = 0;
Index < Size;
++Index)
{
uint32_t SortKey = SortKeyToU32(Source[Index]);
uint32_t Key = (SortKey >> Bit) & 0xFF;
++ArrayOfValues[Key];
}
int Sum = 0;
for (int Index = 0;
Index < ArraySize(ArrayOfValues);
++Index)
{
uint32_t Count = ArrayOfValues[Index];
ArrayOfValues[Index] = Sum;
Sum += Count;
}
for(int Index = 0;
Index < Size;
++Index)
{
uint32_t SortKey = SortKeyToU32(Source[Index]);
uint32_t Key = (SortKey >> Bit) & 0xFF;
Dest[ArrayOfValues[Key]++] = Source[Index];
}
int* Temp = Source;
Source = Dest;
Dest = Temp;
}
}
#include <iostream>
int main() {
int a[] = {1000, -200, 800, -300, 900, -100};
int * p = &a[0];
RadixSort(&p, ArraySize(a));
for (auto x: a)
std::cout << x << " ";
}
输入:
{1000, -200, 800, -300, 900, -100}
输出(正确的,新的排序键):
-300 -200 -100 800 900 1000
输出(不正确,原始排序键):
-100 -200 -300 800 900 1000
我很难找到用于使用基数排序算法进行排序的正确值。 我已经正确地实施了它,但是我对底片有疑问。我试着用二进制来反转值。它对我有一点帮助,但底片是按升序排列的,而不是按降序排列的。最有趣的是,排序适用于浮点数和有符号整数。
这是我构建排序键的函数:
uint32_t SortKeyToU32(int Value)
{
uint32_t Result = (uint32_t)Value;
if(Result & 0x80000000)
{
Result = ~Result;
}
else
{
Result |= 0x80000000;
}
return Result;
}
这是我的排序函数:
void RadixSort(int** Array, int Size)
{
int* Dest = new int[Size];
int* Source = *Array;
memset(Dest, 0, Size*sizeof(int));
for(int Bit = 0;
Bit < 32;
Bit += 8)
{
uint32_t ArrayOfValues[256] = {};
for(int Index = 0;
Index < Size;
++Index)
{
uint32_t SortKey = SortKeyToU32(Source[Index]);
uint32_t Key = (SortKey >> Bit) & 0xFF;
++ArrayOfValues[Key];
}
int Sum = 0;
for (int Index = 0;
Index < ArraySize(ArrayOfValues);
++Index)
{
uint32_t Count = ArrayOfValues[Index];
ArrayOfValues[Index] = Sum;
Sum += Count;
}
for(int Index = 0;
Index < Size;
++Index)
{
uint32_t SortKey = SortKeyToU32(Source[Index]);
uint32_t Key = (SortKey >> Bit) & 0xFF;
Dest[ArrayOfValues[Key]++] = Source[Index];
}
int* Temp = Source;
Source = Dest;
Dest = Temp;
}
}
但是我该如何处理有符号整数的排序呢?对不起,如果它看起来很明显。谢谢
编辑。 这是示例数组输入:1, 6, 9, 2, 3, -4, -10, 8, -30, 4
输出:-4、-10、-30、1、2、3、4、6、8、9
您需要的排序键公式非常简单:
uint32_t SortKeyToU32(int32_t Value) {
return uint32_t(Value) + (1U << 31);
}
下面的原因。首先,我们从 32 位有符号转换为无符号。此转换只是将有符号值的位重新解释为无符号值。
让我们看看有符号值是如何在数字的值 space 中显示的。为简单起见,让我们看一下 4 位有符号数,它总共有 16 个不同的值映射如下:
签署表格:
0, 1, 2, 3, 4, 5, 6, 7, -8, -7, -6, -5, -4, -3, -2, -1
未签名的形式:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
在有符号的情况下,前半部分值是 non-negative 升序排列,后半部分也是负值也是升序排列。
为了排序,我们需要所有负值排在正值之前,并且也按升序排列。对于上面的有符号 4 位值(无符号形式),我们只需要添加 8
,这恰好是范围的中间。因此,整个范围将随着溢出向右移动,负值将出现在正数之前(第一个数字下方是添加 8
后的数字,第二个数字(括号中)是原始数字(添加前)):
0 (-8), 1 (-7), 2 (-6), 3 (-5), 4 (-4), 5 (-3), 6 (-2), 7 (-1), 8 (0), 9 (1), 10 (2), 11 (3), 12 (4), 13 (5), 14 (6), 15 (7)
这正是我在排序键公式中所做的
uint32_t(Value) + (1U << 31)
我 reinterpret-casted 签署了无符号形式并添加了 middle-range 值,即 (1U << 31)
.
使用这个更正后的公式,您的代码可以正常工作,在下面的代码片段中,我也将您的原始排序键公式保留在名称 SortKeyToU32Old()
下,您可以更改排序键函数的名称以查看它之前的工作方式(错误地)并在(正确地)更改我的示例数组之后。
#include <cstdint>
#include <cstring>
#define ArraySize(a) (sizeof(a) / sizeof(a[0]))
uint32_t SortKeyToU32(int32_t Value) {
return uint32_t(Value) + (1U << 31);
}
uint32_t SortKeyToU32Old(int Value)
{
uint32_t Result = (uint32_t)Value;
if(Result & 0x80000000)
{
Result = ~Result;
}
else
{
Result |= 0x80000000;
}
return Result;
}
void RadixSort(int** Array, int Size)
{
int* Dest = new int[Size];
int* Source = *Array;
memset(Dest, 0, Size*sizeof(int));
for(int Bit = 0;
Bit < 32;
Bit += 8)
{
uint32_t ArrayOfValues[256] = {};
for(int Index = 0;
Index < Size;
++Index)
{
uint32_t SortKey = SortKeyToU32(Source[Index]);
uint32_t Key = (SortKey >> Bit) & 0xFF;
++ArrayOfValues[Key];
}
int Sum = 0;
for (int Index = 0;
Index < ArraySize(ArrayOfValues);
++Index)
{
uint32_t Count = ArrayOfValues[Index];
ArrayOfValues[Index] = Sum;
Sum += Count;
}
for(int Index = 0;
Index < Size;
++Index)
{
uint32_t SortKey = SortKeyToU32(Source[Index]);
uint32_t Key = (SortKey >> Bit) & 0xFF;
Dest[ArrayOfValues[Key]++] = Source[Index];
}
int* Temp = Source;
Source = Dest;
Dest = Temp;
}
}
#include <iostream>
int main() {
int a[] = {1000, -200, 800, -300, 900, -100};
int * p = &a[0];
RadixSort(&p, ArraySize(a));
for (auto x: a)
std::cout << x << " ";
}
输入:
{1000, -200, 800, -300, 900, -100}
输出(正确的,新的排序键):
-300 -200 -100 800 900 1000
输出(不正确,原始排序键):
-100 -200 -300 800 900 1000