基数排序得到正确的键对有符号整数进行排序

Question

我很难找到用于使用基数排序算法进行排序的正确值。我已经正确地实施了它，但是我对底片有疑问。我试着用二进制来反转值。它对我有一点帮助，但底片是按升序排列的，而不是按降序排列的。最有趣的是，排序适用于浮点数和有符号整数。

这是我构建排序键的函数：

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

Answer 1

您需要的排序键公式非常简单：

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() 下，您可以更改排序键函数的名称以查看它之前的工作方式（错误地）并在（正确地）更改我的示例数组之后。

Try it online!

#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

基数排序得到正确的键对有符号整数进行排序

Radix sort get the right key to sort signed integers

c++

algorithm

sorting

radix-sort