algorithm - 对十亿学生列表进行排序

Question

在每次面试的问题中，我被问到“你如何根据他们在考试中的总分对十亿学生的名单进行排序？学生从 1-1B 移动的卷数和分数范围是 10-100 。” 虽然任何排序算法都可以，但什么是有效的？

Answer 1

只需对输入运行计数排序O(n)，在这种情况下，因为范围是有界的。这也是最有效的方式，因为任何输出所有学生的方式都需要 Ω(n)。

您可以通过循环输出学生以获得可能的可用分数（例如，如果存在 90 个可能的分数，则循环遍历学生 90 次，第一次输出分数为 100 的学生，...）。

这个任务可以通过桶排序来完成。但首先你应该遍历输入，找到每个分数相关的学生人数，然后通过考虑学生人数为每个分数创建一个桶，然后填充桶，注意你应该为桶创建一个数组，你也应该有一个额外参数，用于保存每个桶中的当前项目数。

第一种方法（直接使用计数排序）是 O(n) 和 O(1) 额外空间，第二种方法是 O(n) 和 O(n) 额外空间，但第二种方法更快，因为它是2*n，而第一种方法是90*n。

Answer 2

使用计数排序。如果您知道该问题中满足的最大值和其他一些参数，那就太好了。它以 O(n) 排序

Answer 3

我将使用某种分而治之的算法（例如合并排序或快速排序或桶排序），并使用这种思想在几个桶之间划分排序。当您需要将所有数据合并回一个大数组时，就会出现问题，但这只需要 O(n)，因为子数组已经排序。

bucket sort(L)
{
list Y[k+1]
for (i = 0; i <= k; i++) Y[i] = empty
while L nonempty
{
    let X = first record in L
    move X to Y[key(X)]
}
for (i = 0; i <= k; i++)
concatenate Y[i] onto end of L
}

有两个循环花费 O(k) 时间，一个花费 O(n)，所以总时间是 O(n+k)。当 k 小于 n 时，这很好。例如，假设您想按分数对 1,000,000,000 人进行排序；n=1000000000，k=100-10，所以时间 = O(n)。