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

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];

现在它将每个学生放在他/她的桶的末尾,并递减该桶的位置值.

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

关于这种排序的好处是它是O(n),而不是O(n*log(n)).但是,它仅适用于可以离散为有限(且可管理)数量的桶的东西.

这段代码有点滑稽的一点是它颠倒了具有相同等级的学生的顺序.您可以通过将累积计数更改为存储区起始位置并在填充NS时递增它们,或者更容易,在最后一个循环中向后遍历S,将其修改为稳定排序.