C++基数排序按位运算

我想了解基数排序如何处理按位，所以我在互联网上找到了这个算法，但我不明白它是如何工作的！C++基数排序按位运算

#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; 
}

任何人都可以请解释这个工作如何排序整数！非常感谢

来源

2013-06-11 satyres

不要试图从代码学习算法，这太难了，你最终会学习错误的东西。从一本书或网页或人员学习。 https://en.wikipedia.org/wiki/Radix_sort –

我有一个关于使用按位基数算法的想法，但我想了解它如何使用这种算法，并在维基百科他们不谈论按位运算 – satyres

哦，我误解，并认为你正在尝试学习基数种类。对不起 –

好了，你说你明白一个MSD基数排序是如何工作的，所以在这种情况下，关键的部分是：

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

的radix_test是functionoid，当给定值和测试该位是否未在给定值中设置。 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位（位编号31），并使用std::partition把所有的值与该位未在左侧设置，并在该位是在右边设置的值。然后它在下一个较小位的两半上递归。到达最后时，数据被排序。

由于此实现在单比特级别（因此基数为2）上工作，因此这实际上是快速排序。基数排序可以真正发光，当你改变他们与更多的组（非就地）一起工作，但它高度依赖于数据的类型和数量。有40亿个使用全部值的整数，我可能会使用524288个桶而不是2个，然后不用递归，而只需切换到一个introsort。

来源

2013-06-11 18:35:39

哇！非常好的解释非常感谢，但如果你不介意，我有一些问题！ – satyres

C++基数排序按位运算

回答

相关问题