如何按成绩对学生记录数组进行排序

Question

大家好，我现在正在准备考试，我似乎不能理解这个概念。问题是，如果给定一个学生记录数组，其中记录的成员是学生姓名和他们的成绩，那么如何按成绩对其进行排序。这位教授举了一个他称之为“分布式计数排序”的例子。我很难理解它，希望有人能给我下面代码的伪代码或算法，谢谢:)

Function Distribution_counting_sort(S, n){
//Input: a student array S of n records
//Output: a sorted array (wrt grade) NS
int count[101]; /*init to 0’s */
/* counting */
for (i = 0; i < n; i++) count[S[i].grade]++;
/* accumulating */
count[0]--;
for (i = 1; i < 101; i++) count[i] = count[i -1] + count[i];
/* distribution */
for (i = 0; i < n; i++) NS[count[S[i].grade]--] = S[i];

Answer 1

这本质上是Bucket Sort的一个变体。

这些是存储桶，每个可能的等级一个：

int count[101]; /*init to 0’s */

这计算了每个年级有多少学生。这告诉我们每个存储桶的大小：

for (i = 0; i < n; i++) count[S[i].grade]++;

这会将计数转换为累积计数。这为我们提供了目标数组中每个存储桶的结束位置。我相信，count[0]--位是为了说明基于0的数组。

count[0]--;
for (i = 1; i < 101; i++) count[i] = count[i -1] + count[i];

现在它将每个学生放在他/她的存储桶的末尾，并递减该存储桶的position值。

for (i = 0; i < n; i++) NS[count[S[i].grade]--] = S[i];

这种排序的好处是它是O(n)，而不是O(n*log(n))。然而，它只适用于可以离散到有限(且可管理)数量的存储桶中的事物。

这段代码的一个有趣之处在于，它颠倒了具有相同成绩的学生的顺序。您可以将其修改为稳定的排序，方法是将累积计数更改为存储桶的起始位置，并在填充NS时递增它们，甚至可以更容易地在最后一个循环中向后遍历S。

Answer 2

有101个年级，从0到100

int count[101]; /*init to 0’s */

用每个等级的总分填写count[]，例如，count90=4表示四个人得了90分

for (i = 0; i < n; i++) count[S[i].grade]++;

接下来，将这些总数转换为连续计数，即如果57人低于90，则count90 = 57 + 4或61。因此，对于每一次计数，你都有得到该分数或更低分数的人数。这对于最终的数组很重要...最终数组中需要61个元素才能容纳所有得分在90或更低的人。请注意，传入的count100应该=n。

count--将整个计数向下移位1，这会将从1开始的最终数组转换为从0开始的最终数组，例如，如果我有一个人得到了0，count =1，那么我的最终数组将从NS1开始。我想从NS开始。所以上面的61个元素现在是60

count[0]--;
for (i = 1; i < 101; i++) count[i] = count[i -1] + count[i];

最后(希望他不再重复使用'i')，找到每个年级的位置……如果有60个人的'90‘或更低，那么'90’分属于最后一个数组NS的第60个元素。这是令人困惑的，部分原因是因为“--”...记住，“90”级有60分，所以你来的第一个“90”会被放在NS60，因为有59个人的成绩较低。'90‘的计数递减到59，因此下一个'90’将放在NS59。以此类推。

for (i = 0; i < n; i++) NS[count[S[i].grade]--] = S[i];

最终结果是从最低级别到最高级别的阵列，其中NS是最低级别，NSn是最高级别。

讲得通?这真是一个漂亮的算法！