首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >存储桶排序还是合并排序?

存储桶排序还是合并排序?
EN

Stack Overflow用户
提问于 2021-11-13 04:54:46
回答 3查看 150关注 0票数 1

我正在做一个c++作业,我必须对数据(n=400)进行排序,它是从0到100的学生分数。我对使用存储桶排序感到困惑,它将算法排序到存储桶中,或者合并排序,它将算法分开并征服。我应该使用哪一个?为什么?

EN

回答 3

Stack Overflow用户

发布于 2021-11-13 05:08:23

更新

先读一下托马斯·梅伦德的回答。他对这个具体问题提供了更相关的答案。由于分数可能是整数,直方图排序(桶排序的变体)应该比合并排序更快!

当数据集分布不好时,存储桶排序的性能很差,因为大多数项目都会落入几个流行的存储桶中。在您的情况下,可以合理地假设大多数学生的分数或多或少都在中位数附近,只有很少的异常值。因此,我认为合并排序在此上下文中执行得更好,因为它不受数据集分布的影响。

其他注意事项

如果我们可以根据数据集的预期分布来调整桶范围,那么可能会有这样的争论,即桶排序更好。当然,如果我们中了大奖并很好地预测了分布,它可以显着加快排序过程。然而,这样做的缺点是当我们的预测出错时,排序性能可能会直线下降,即获得意想不到的数据集。例如,测试太容易/太难可能会导致这个问题上下文中的“意想不到的数据集”。换句话说,桶排序具有更好的最佳情况时间复杂度,而合并排序具有更好的最坏情况时间复杂度。用于比较算法的度量标准取决于每个应用程序的需求。在实践中,最坏情况下的时间复杂度通常被发现更有用,我认为对于这个特定的问题也可以这样说。这也是一个优点,如果我们使用合并排序,我们就不会遭受计算/调整桶范围的额外成本。

票数 2
EN

Stack Overflow用户

发布于 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后面的开销很重要,然后可能就不那么简单了。

也就是说,桶排序的开销通常比合并排序的开销小。您需要为一些计数分配一个数组,并为输出分配一个数组,然后您需要对输入运行两次,第一次是计数,然后是排序。简单的存储桶排序可能如下所示:

代码语言:javascript
运行
复制
#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个元素,并且不需要为这样的事情实现新的排序算法。然而,对于一个练习,做一些测量和实验可能是很有趣的。

票数 2
EN

Stack Overflow用户

发布于 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,并使用适当的比较函数。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/69951566

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档