我正在做一个 C++ 作业，我必须对数据(n=400)进行排序，这是从 0-100 的学生分数。我对使用桶排序(将算法排序到桶中)或合并排序(分而治之)感到困惑。我应该使用哪一个？为什么？
最佳答案
更新
首先阅读 Thomas Mailund 的回答。他对这个具体问题提供了更相关的答案。由于分数可能是整数，因此直方图排序(桶排序的变体)应该比合并排序更快!
当数据集分布不均匀时，桶排序表现不佳，因为大多数项目都会落入几个受欢迎的桶中。就您的情况而言，可以合理地假设大多数学生分数或多或少都在中位数分数附近，并且只有很少的异常值。因此，我认为合并排序在这种情况下表现更好，因为它不受数据集分布的影响。
额外考虑
可能有人认为，如果我们可以根据数据集的预期分布调整存储桶范围，存储桶排序会更好。当然，如果我们中了大奖并且很好地预测了分布，它可以显着加快排序过程。然而，这样做的缺点是，当我们的预测出错时，即得到意外的数据集时，排序性能可能会直线下降。例如，测试太简单/太困难可能会导致在这个问题的上下文中出现“意外的数据集”。换句话说，桶排序具有更好的最佳情况时间复杂度，而合并排序具有更好的最坏情况时间复杂度。使用哪种指标来比较算法取决于每个应用程序的需求。在实践中，通常发现最坏情况的时间复杂度更有用，我认为对于这个特定问题也可以这样说。这也是一个优点，如果我们进行合并排序，我们就不会遭受计算/调整存储桶范围的额外成本。
关于c++ - 桶排序还是归并排序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/69951566/