使用C++的基數排序

Question

假設我有一堆數字。我必須先將最不重要的數字放入相應的桶中。例如：530，我得先放入桶0。61號，我必須投入桶1.

我計劃用一個多維數組來做到這一點。所以，我創建了一個2-dimenional陣列，這是NROWS 10（0〜9）和ncolumns是999999（因爲我不知道怎麼會大名單定）：

int nrows = 10; 
    int ncolumns = 999999; 

    int **array_for_bucket = (int **)malloc(nrows * sizeof(int *)); 
     for(i = 0; i < nrows; i++) 
      array_for_bucket[i] = (int *)malloc(ncolumns * sizeof(int)); 

    left = (a->value)%10; 
    array_for_bucket[left][?? ] = a->value; 

然後，我創建了一個節點打個電話。在這個節點a中，存在一個值50.爲了找出我想要放入哪個桶，我計算「左」，並得到0.所以我想把這個a->值放入桶0中。但是現在我我卡住了。我該如何把這個價值放入桶中？我必須使用指針數組來做到這一點。

我想了很長時間，但還是沒能找到一個很好的辦法做到這一點。所以請與我分享一些想法。謝謝！

Answer 1

有一個更簡單的方法來做到這一點，而不是radix*nkeys空間，你只需要一個nkeys大小的緩衝區。

分配可以容納nkeys密鑰的第二緩衝器中。現在，先對您的數據進行第一遍處理，然後簡單計算每個存儲桶中有多少個密鑰。您現在可以創建一個大小爲radix的指針數組，其中每個指針指向輸出緩衝區中該存儲桶的起始位置。最後，第二遍通過數據移動鍵。每次移動一個鍵時，增加該桶指針。

下面是一些C代碼，使之成爲C++：

void radix_sort(int *keys, int nkeys) 
{ 
    int *shadow = malloc(nkeys * sizeof(*keys)); 

    int bucket_count[10]; 
    int *bucket_ptrs[10]; 
    int i; 

    for (i = 0; i < 10; i++) 
     bucket_count[i] = 0; 

    for (i = 0; i < nkeys; i++) 
     bucket_count[keys[i] % 10]++; 

    bucket_ptrs[0] = shadow; 
    for (i = 1; i < 10; i++) 
     bucket_ptrs[i] = bucket_ptrs[i-1] + bucket_count[i-1]; 

    for (i = 0; i < nkeys; i++) 
     *(bucket_ptrs[keys[i] % 10]++) = keys[i]; 

    //shadow now has the sorted keys 

    free(shadow); 
} 

但我可能誤解了這個問題。如果你正在做一些與基數不同的事情，請加一些細節。

Answer 2

，如果你想存儲指針看看了Boost Pointer containers庫。

Answer 3

C++是不是我的強項，但是從wikipedia-Raidx Sort這個代碼是非常全面的，可能更多的是C++ - ISH比到目前爲止你已經實現了什麼。希望它可以幫助

Answer 4

這是C++，我們不使用malloc了。我們使用容器。二維數組是向量的向量。

vector<vector<int> > bucket(10); 
left = (a->value)%10; 
bucket[left].push_back(a->value);