我正在做一個 C 作業，我必須對資料 (n=400) 進行排序，這些資料是 0-100 的學生分數。我對使用桶排序感到困惑，桶排序將演算法分類為桶或歸并排序，分而治之。我應該使用哪一種，為什么？
uj5u.com熱心網友回復：
更新
首先閱讀 Thomas Mailund 的回答。他為這個特定問題提供了更相關的答案。由于分數可能是整數，直方圖排序（桶排序的變體）應該比歸并排序快！
當資料集分布不好時，桶排序的性能很差，因為大多數專案將落入幾個流行的桶中。在您的情況下，可以合理地假設大多數學生分數或多或少都在中位數附近，并且只有很少的例外值。因此，我認為合并排序在這種情況下表現更好，因為它不受資料集分布的影響。
額外的考慮
如果我們可以根據資料集的預期分布調整桶范圍，則可能存在一種說法，即桶排序會更好。當然，如果我們中了頭獎并很好地預測了分布，它可以顯著加快排序程序。然而，這樣做的缺點是當我們的預測出錯時排序性能可能會下降，即獲得意外的資料集。例如，在這個問題的背景關系中，測驗太容易/太難可能會導致這個“意外的資料集”。換句話說，桶排序具有更好的最佳情況時間復雜度，而歸并排序具有更好的最壞情況時間復雜度。用于比較演算法的指標取決于每個應用程式的需求。在實踐中，通常發現最壞情況的時間復雜度更有用，我認為對于這個特定問題也可以這樣說。如果我們進行歸并排序，我們不會因計算/調整桶范圍而遭受額外成本，這也是一個優點。
uj5u.com熱心網友回復：
答案取決于您的資料。但是，合并排序將以 O(n log n) 運行，而桶排序將以 O(n b) 運行，其中 b 是您擁有的桶數。如果分數從 0 到（包括）100，那么 b 是 101。所以問題是 O(n log n) 比 O(n 101) 運行得更快，這是一個理論上容易回答的問題，因為 O(n 101) = O(n) 顯然 O(n) 比 O(n log n) 快。即使我們做了用 n 替換 400 的（公認的愚蠢）練習，我們也會得到 501 進行桶排序，并且 log2(400) = 9（四舍五入）3600 進行歸并排序。但這很愚蠢，因為大 O 符號不能那樣作業。從理論上講，我們只會得出結論，O(n) 優于 O(n log n)。
但這是理論上的答案。實際上，隱藏在大 O 背后的開銷很重要，然后它可能并不那么簡單。
話雖如此，桶排序的開銷通常小于歸并排序。您需要為一些計數分配一個陣列和一個陣列來放置輸出，然后您需要遍歷輸入兩次，首先是計數，然后是排序。一個簡單的桶排序可能如下所示：
#include <iostream>
#include <string>
// Some fake data
struct student
{
int score;
std::string name;
};
struct student scores[] = {
{45, "jack"},
{12, "jill"},
{99, "john"},
{89, "james"}};
void bucket_sort(int n, struct student in[n], struct student out[n])
{
int buckets[101]; // range 0-100 with 100 included
for (int i = 0; i < 101; i )
{
buckets[i] = 0;
}
// get offsets for each bucket
for (int i = 0; i < n; i )
{
buckets[in[i].score] ;
}
int acc = 0;
for (int i = 0; i < 101; i )
{
int b = buckets[i];
buckets[i] = acc;
acc = b;
}
// Bucket the scores
for (int i = 0; i < n; i )
{
out[buckets[in[i].score] ] = in[i];
}
}
void print_students(int n, struct student students[n])
{
for (int i = 0; i < n; i )
{
std::cout << students[i].score << ' ' << students[i].name << std::endl;
}
std::cout << std::endl;
}
int main(void)
{
int no_students = sizeof scores / sizeof scores[0];
print_students(no_students, scores);
struct student sorted[no_students];
bucket_sort(no_students, scores, sorted);
print_students(no_students, sorted);
return 0;
}
（原諒我的 C ，自從我使用這門語言已經 10 多年了，所以代碼看起來可能比它應該的更像 C）。
在實踐中找出更快的最佳方法當然是對其進行測量。std::sort與上面類似的內容進行比較，您應該會得到答案。
但是，如果不是為了作業，我不建議您進行實驗。內置std::sort可以輕松地以比您需要的速度更快地處理 400 個元素，并且不需要為類似的東西實作新的排序演算法。但是，對于練習，進行一些測量和實驗可能會很有趣。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/362895.html
上一篇：kotlin：對List<T>進行排序，其中T是一個類
下一篇：輸入0與層inception_v3不兼容預期形狀=(None,299,299,3),foundshape=(1,229,229,3)