桶排序實現

我要實現一個桶排序，以便它排序的陣列size = 100與0和100桶我之間隨機生成的數字如下：桶排序實現

Bucket0: (0<=x<10) 
Bucket1: (10<=x<20) 
. 
. 
. 
Bucket9: (90<=x<100)

現在我明白了背後的理論bucket排序，在那裏我將元素插入到每個單獨的存儲桶中，但是我不知道如何實際創建存儲桶。我是否創建了一個數組，如B，而桶本身就是數組？或者是用整數實現一個桶的更爲標準的方式？

我只需要在正確的方向輕推，謝謝任何幫助！

來源

2017-10-13 zsloan112

你到目前爲止嘗試過什麼？ – JGroven

你需要顯示你的努力來解決這個問題。如果您需要指導或指導，請嘗試[Codementor]（https://www.codementor.io），[Savvy]（https://www.savvy.is），[Hackhands]（https://hackhands.com））或[airpair]（https://www.airpair.com）。 – tadman

您應該使用[bucket sort]（https://en.wikipedia.org/wiki/Bucket_sort）的哪種變體來完成此作業？ – rcgldr

是的。
你必須聲明長度爲101的另一個數組（我們可以說b）。長度代表我們數字的範圍。

現在你必須在第一個數組和每個單元格上，並且當你找到每個數字k（0 < = k < = 100）時，你必須++ b [k]。例如：b[a[i]]++;

現在我們有數組b，它表示每個數字k在第一個數組中出現的次數。我們可以覆蓋第一陣列：

for(int i = 0; i <= RANGE; i++) 
    for(int j = 0; j < b[i]; j++) 
     a[p++] = i;

而在你的情況下，範圍是100

複雜度：O（N）

請注意，我們可以實現一個變量，而不是使用數組，這是做同樣的事情，但每次都有不同的數字。節省不多，但節省一點空間的複雜性。

來源

2017-10-13 16:40:53 Yinon

這就是[計數排序]（https：// en .wikipedia.org/wiki/Counting_sort＃Variant_algorithms），它可以被認爲是[bucket sort]（https://en.wikipedia.org/wiki/Bucket_sort）的變體之一。 OP沒有說明要使用哪種桶式排序變量。 – rcgldr

回答

相關問題