如何獲取BucketSort算法的工作？

我想在C++中創建一個bucketsort算法，但它根本不起作用。每一次運行，它都會向陣列中添加許多新數字，通常非常大，例如數十億。有人知道爲什麼嗎？這裏是代碼 - （請注意，我傳遞了一個大小爲100的數組，其中的隨機數從0到〜37000，並且插入排序函數功能齊全並已多次測試）如何獲取BucketSort算法的工作？

將不勝感激如果有人能指出什麼是錯的。

void bucketSort(int* n, int k) 
{ 
    int c = int(floor(k/10)), s = *n, l = *n; 
    for(int i = 0; i < k; i++) { 
     if(s > *(n + i)) s = *(n + i); 
     else if(l < *(n + i)) l = *(n + i); 
    } 
    int bucket[c][k + 1]; 
    for(int i = 0; i < c; i++) { 
     bucket[i][k] = 0; 
    } 

    for(int i = 0; i < k; i++) { 
     for(int j = 0; j < c; j++) { 
      if(*(n + i) >= (l - s)*j/c) { 
       continue; 
      } else { 
       bucket[j][bucket[j][k]++] = *(n + i); 
       break; 
      } 
     } 
    } 

    for(int i = 0; i < c; i++) { 
     insertionSort(&bucket[i][0], k); 
    } 
}

來源

2013-02-16 Cisplatin

'bucket [j] [bucket [j] [k] ++] = *（n + i）;'這真的是你的意思嗎？它看起來錯了。 – us2012 2013-02-16 18:46:10

我用作指數使用的計數器的最後一個索引;我沒看到那條線有什麼問題 – Cisplatin 2013-02-16 18:51:42

爲什麼你用'*（n + i）'代替'n [i]'？你是從一本很糟糕的書或教程中得到的嗎？ – Blastfurnace 2013-02-16 20:36:15

該行不編譯。 int bucket[c][k + 1];

我認爲問題在於你的桶指數。這部分在這裏

for(int j = 0; j < c; j++) { 
    if(*(n + i) >= (l - s)*j/c) { 
     continue; 
    } else { 
     bucket[j][bucket[j][k]++] = *(n + i); 
     break; 
    } 
}

沒有做等價的：

insert n[i] into bucket[ bucketIndexFor(n[i]) ]

首先，它由一個獲取索引斷開。正因爲如此，它也錯過了最後一桶的數字。還有一個小錯誤，因爲索引計算使用範圍[0,l-s]而不是[s,l]，這隻有在s等於0時才相同。

當我寫bucketIndex爲：

int bucketIndex(int n, int c, int s, int l) 
{ 
    for(int j = 1; j <= c; j++) { 
     if(n > s + (l-s)*j/c) { 
      continue; 
     } else { 
      return j-1; 
     } 
    } 
    return c-1; 
}

和重寫你的算法的主要部分爲：

std::vector< std::vector<int> > bucket(c); 

for(int i = 0; i < k; i++) { 
    bucket[ bucketIndex(n[i], c, s, l) ].push_back(n[i]); 
}

我得到正確地插入他們的桶中的項目。

來源

2013-02-16 19:54:03 Thomas

如何獲取BucketSort算法的工作？

回答

相關問題