非常基本的基數排序

Question

我剛寫了一個簡單的迭代基數排序，我想知道我是否有正確的想法。
遞歸實現似乎更爲常見。

我正在排序4個字節的整數（無符號以保持簡單）。
我使用1個字節作爲'數字'。所以我有2^8 = 256個桶。
我正在排序最重要的數字（MSD）。
每次排序後，我將它們按照它們在桶中存在的順序放回到數組中，然後執行下一個排序。
所以我最終做了4個桶的排序。
它似乎適用於一小部分數據。由於我正在做MSD，我猜測這不穩定，可能會因不同的數據而失敗。

我錯過了什麼重要的？

#include <iostream> 
#include <vector> 
#include <list> 

using namespace std; 

void radix(vector<unsigned>&); 
void print(const vector<list<unsigned> >& listBuckets); 
unsigned getMaxForBytes(unsigned bytes); 
void merge(vector<unsigned>& data, vector<list<unsigned> >& listBuckets); 

int main() 
{ 
    unsigned d[] = {5,3,6,9,2,11,9, 65534, 4,10,17,13, 268435455, 4294967294,4294967293, 268435454,65537}; 
    vector<unsigned> v(d,d+17); 

    radix(v); 
    return 0; 
} 

void radix(vector<unsigned>& data) 
{ 
    int bytes = 1;         // How many bytes to compare at a time 
    unsigned numOfBuckets = getMaxForBytes(bytes) + 1; 
    cout << "Numbuckets" << numOfBuckets << endl; 
    int chunks = sizeof(unsigned)/bytes; 

    for(int i = chunks - 1; i >= 0; --i) 
    { 
     vector<list<unsigned> > buckets;   // lazy, wasteful allocation 
     buckets.resize(numOfBuckets); 

     unsigned mask = getMaxForBytes(bytes); 
     unsigned shift = i * bytes * 8; 
     mask = mask << shift; 

     for(unsigned j = 0; j < data.size(); ++j) 
     { 
      unsigned bucket = data[j] & mask;  // isolate bits of current chunk 
      bucket = bucket >> shift;    // bring bits down to least significant 

      buckets[bucket].push_back(data[j]); 
     } 

     print(buckets); 

     merge(data,buckets); 
    } 
} 

unsigned getMaxForBytes(unsigned bytes) 
{ 
    unsigned max = 0; 
    for(unsigned i = 1; i <= bytes; ++i) 
    { 
     max = max << 8; 
     max |= 0xFF; 
    } 

    return max; 
} 

void merge(vector<unsigned>& data, vector<list<unsigned> >& listBuckets) 
{ 
    int index = 0; 
    for(unsigned i = 0; i < listBuckets.size(); ++i) 
    { 
     list<unsigned>& list = listBuckets[i]; 
     std::list<unsigned>::const_iterator it = list.begin(); 

     for(; it != list.end(); ++it) 
     { 
      data[index] = *it; 
      ++index; 
     } 
    } 
} 

void print(const vector<list<unsigned> >& listBuckets) 
{ 
    cout << "Printing listBuckets: " << endl; 
    for(unsigned i = 0; i < listBuckets.size(); ++i) 
    { 
     const list<unsigned>& list = listBuckets[i]; 

     if(list.size() == 0) continue; 

     std::list<unsigned>::const_iterator it = list.begin(); // Why do I need std here!? 
     for(; it != list.end(); ++it) 
     { 
      cout << *it << ", "; 
     } 

     cout << endl; 
    } 
} 

更新：
似乎在LSD的形式，它可以通過基數改變塊循環進行修改以及工作方式如下：

for(int i = chunks - 1; i >= 0; --i) 

Answer 1

讓我們來看看恩例如用兩位十進制數字：

49, 25, 19, 27, 87, 67, 22, 90, 47, 91 

按第一位數排序得到

19, 25, 27, 22, 49, 47, 67, 87, 90, 91 

接下來，排序第二位，產生

90, 91, 22, 25, 27, 47, 67, 87, 19, 49 

好像不對，不是嗎？或者這不是你在做什麼？如果我弄錯了，也許你可以告訴我們代碼。

如果您對具有相同第一位數字的所有組執行第二種排序，則您的算法將等同於遞歸版本。它也會保持穩定。唯一的區別是你會按照廣度優先而不是深度優先的方式進行排序。

Answer 2

您還需要確保在重組之前將每個桶從MSD排序到LSD。 示例： 19,76,90,34,84,12,72,38 在MSD上分爲10個桶[0-9] B0 = []; B1 = [19,12]; B2 = []; B3 = [34,38]; B4 = []; B5 = []; B6 = []; B7 = [76,72]; B8 = [84]; B9 = [90]; 如果你要重新組裝，然後再次排序它不會工作。而是遞歸地對每個桶進行排序。 B1被分類到B1B2 = [12]; B1B9 = [19] 一旦所有已經排序，您可以正確地重新組裝。