我正在做一项c++作业，我必须对数据(n=400(进行排序，这些数据是0-100之间的学生分数。我对使用bucket排序(将算法排序为bucket(或merge排序(分割并征服(感到困惑。我应该使用哪一个？为什么？
答案取决于您的数据。但是，合并排序将在O(n log n(中运行，而桶排序将在0(n+b(中运行。其中b是您拥有的桶数。如果分数从0到(包括(100，则b为101。因此，问题是O(n-logn(比O(n+101(运行得更快，这在理论上是一个很容易回答的问题，因为O(n+101(=O(n(，显然O(n。即使我们用n代替400，我们也会得到501作为bucket排序，log2(400(=9(四舍五入(3600作为merge排序。但这很愚蠢，因为big-O表示法不起作用。从理论上讲，我们可以得出结论，O(n(比O(n-logn(好。
但这是理论上的答案。在实践中，隐藏在大O后面的开销很重要，而且可能没有那么简单。
也就是说，bucket排序的开销通常比merge排序的要小。你需要为一些计数分配一个数组，并为输出分配一个阵列，然后你需要对输入运行两次，首先是计数，然后是排序。一个简单的桶排序可能是这样的：
#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个元素，并且不需要为类似的事情实现新的排序算法。不过，对于锻炼来说，做一些测量和实验可能会很有趣。
更新
先读托马斯·梅伦德的答案。他对这个具体问题提供了更切合实际的答案。由于分数可能是整数，所以直方图排序(bucket排序的变体(应该比合并排序更快！
Bucket排序在数据集分布不好时表现不佳，因为大多数项目都会落入少数流行的Bucket中。在你的情况下，可以合理地假设大多数学生的分数或多或少都在中间分数附近，只有很少的异常值。因此，我认为合并排序在这种情况下表现更好，因为它不受数据集分布的影响。
额外对价
如果我们可以根据数据集的预期分布来调整bucket范围，那么bucket排序可能会更好。当然，如果我们中了大奖并很好地预测了分布，它可以显著加快排序过程。然而，这样做的缺点是，当我们的预测出错时，即获得意外的数据集时，排序性能可能会直线下降。例如，测试太容易/太难可能导致这种"错误"；意外数据集"；在这个问题的背景下。换句话说，桶排序具有更好的最佳情况时间复杂性，而合并排序则具有更好的最坏情况时间复杂性。用于比较算法的度量取决于每个应用程序的需要。在实践中，最坏情况下的时间复杂性通常被发现更有用，我认为对于这个特定的问题也是如此。此外，如果我们选择合并排序，我们不会承担计算/调整存储桶范围的额外成本。
这个问题不够精确：我必须对数据(n=400(进行排序，这是0-100之间的学生分数。
如果等级是整数，则每个等级有一个桶的桶排序，也称为直方图排序或计数排序，将在线性时间内完成任务，如Thomas Mailund的回答所示。
如果等级是十进制的，bucket排序只会增加复杂性，并且给定样本大小，mergesort在使用经典实现的O(n.log(n((时间内会做得很好。
如果问题的目标是实现排序算法，则以上适用，否则您应该只在C++中使用std::sort或在C中使用具有适当比较函数的qsort。