我正在做一个c++作业,我必须对数据(n=400)进行排序,它是从0到100的学生分数。我对使用存储桶排序感到困惑,它将算法排序到存储桶中,或者合并排序,它将算法分开并征服。我应该使用哪一个?为什么?
发布于 2021-11-13 05:08:23
更新
先读一下托马斯·梅伦德的回答。他对这个具体问题提供了更相关的答案。由于分数可能是整数,直方图排序(桶排序的变体)应该比合并排序更快!
当数据集分布不好时,存储桶排序的性能很差,因为大多数项目都会落入几个流行的存储桶中。在您的情况下,可以合理地假设大多数学生的分数或多或少都在中位数附近,只有很少的异常值。因此,我认为合并排序在此上下文中执行得更好,因为它不受数据集分布的影响。
其他注意事项
如果我们可以根据数据集的预期分布来调整桶范围,那么可能会有这样的争论,即桶排序更好。当然,如果我们中了大奖并很好地预测了分布,它可以显着加快排序过程。然而,这样做的缺点是当我们的预测出错时,排序性能可能会直线下降,即获得意想不到的数据集。例如,测试太容易/太难可能会导致这个问题上下文中的“意想不到的数据集”。换句话说,桶排序具有更好的最佳情况时间复杂度,而合并排序具有更好的最坏情况时间复杂度。用于比较算法的度量标准取决于每个应用程序的需求。在实践中,最坏情况下的时间复杂度通常被发现更有用,我认为对于这个特定的问题也可以这样说。这也是一个优点,如果我们使用合并排序,我们就不会遭受计算/调整桶范围的额外成本。
发布于 2021-11-15 04:15:25
答案取决于你的数据。然而,合并排序将在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个元素,并且不需要为这样的事情实现新的排序算法。然而,对于一个练习,做一些测量和实验可能是很有趣的。
发布于 2021-12-05 15:10:06
这个问题不够精确:我必须对数据进行排序(n=400),它是从0到100的学生分数。
如果分数是整数,每个分数有一个桶的bucket sort,也称为直方图排序或counting sort将在线性时间内完成这项工作,如Thomas Mailund的答案所示。
如果等级是小数,桶排序只会增加复杂性,并且给定样本大小,mergesort在经典实现的O(n.log(n))时间内将做得很好。
如果问题的目标是实现排序算法,那么上面的方法也适用,否则您应该在C++中使用std::sort
,或者在C中使用qsort
,并使用适当的比较函数。
https://stackoverflow.com/questions/69951566
复制相似问题