问存储桶排序还是合并排序？

EN

更新

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

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

其他注意事项

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

答案取决于你的数据。然而，合并排序将在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个元素，并且不需要为这样的事情实现新的排序算法。然而，对于一个练习，做一些测量和实验可能是很有趣的。

这个问题不够精确:我必须对数据进行排序(n=400)，它是从0到100的学生分数。

如果分数是整数，每个分数有一个桶的bucket sort，也称为直方图排序或counting sort将在线性时间内完成这项工作，如Thomas Mailund的答案所示。

如果等级是小数，桶排序只会增加复杂性，并且给定样本大小，mergesort在经典实现的O(n.log(n))时间内将做得很好。

如果问题的目标是实现排序算法，那么上面的方法也适用，否则您应该在C++中使用std::sort，或者在C中使用qsort，并使用适当的比较函数。