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++基數排序按位運算

回答

相關問題