1

我试图了解基数排序如何与按位一起工作，所以我在互联网上找到了这个算法，但我不明白它是如何工作的！

#include <algorithm>
#include <iostream>
#include <iterator>

// Radix sort comparator for 32-bit two's complement integers
class radix_test
{
    const int bit; // bit position [0..31] to examine
public:
    radix_test(int offset) : bit(offset) {} // constructor

    bool operator()(int value) const // function call operator
    {
        if (bit == 31) // sign bit
            return value < 0; // negative int to left partition
        else
            return !(value & (1 << bit)); // 0 bit to left partition
    }
};

// Least significant digit radix sort
void lsd_radix_sort(int *first, int *last)
{
    for (int lsb = 0; lsb < 32; ++lsb) // least-significant-bit
    {
        std::stable_partition(first, last, radix_test(lsb));
    }
}

// Most significant digit radix sort (recursive)
void msd_radix_sort(int *first, int *last, int msb = 31)
{
    if (first != last && msb >= 0)
    {
        int *mid = std::partition(first, last, radix_test(msb));
        msb--; // decrement most-significant-bit
        msd_radix_sort(first, mid, msb); // sort left partition
        msd_radix_sort(mid, last, msb); // sort right partition
    }
}

// test radix_sort
int main()
{
    int data[] = { 170, 45, 75, -90, -802, 24, 2, 66 };

    lsd_radix_sort(data, data + 8);
    // msd_radix_sort(data, data + 8);

    std::copy(data, data + 8, std::ostream_iterator<int>(std::cout, " "));

    return 0;
}

谁能解释一下这是如何对整数进行排序的！非常感谢

4

1 回答 1

2

好吧，您说您了解 MSD 基数排序的工作原理，因此在这种情况下，关键部分是：

class radix_test {
    bool operator()(int value) const // function call operator
    {
        ...
            return !(value & (1 << bit)); // 0 bit to left partition
    }
}

这radix_test是一个函数，当给定一个值和一个位数时，测试该位是否未在给定值中设置。 1<<bit产生该位编号的位掩码，然后value & <bitmask>产生<bitmask>该位是否已设置，0否则产生。然后，如果未设置该位，则该人使用!返回 true。

void msd_radix_sort(... int msb = 31)
{
    if (.... msb >= 0)
    {
        ... std::partition(... radix_test(msb));
        msb--; // decrement most-significant-bit
        msd_radix_sort(..., msb); // sort left partition
        msd_radix_sort(..., msb); // sort right partition
    }
}

排序本身从第 32 位（位 ID 31）开始，并用于std::partition将未设置该位的所有值放在左侧，将设置该位的值放在右侧。然后它用下一个较小的位在两半上递归。到结束时，数据已排序。

由于此实现适用于单个位级别（因此基数为 2），因此这实际上是一种快速排序。当您将基数排序更改为与更多组（而不是就地）一起使用时，基数排序确实可以发挥作用，但它高度依赖于数据的类型和数量。对于使用全部值范围的 40 亿个整数，我可能会使用 524288 个存储桶而不是两个，然后不再递归，而是简单地切换到一个 introsort。

于 2013-06-11T18:35:39.630 回答