如何按成绩对一组学生记录进行排序
大家好，我现在正在准备考试，我似乎无法理解这个概念。 问题是，如果给定一组学生记录，其中记录的成员是学生姓名和成绩，那么如何按成绩对其进行排序。教授给出了他所谓的“分布式计数排序”的例子。我无法理解它，希望有人能给我下面代码的伪代码或算法， 谢谢 ：）
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];
Hey all, im studying for an exam at the moment, and I can't seem to understand this concept.
The question is, if your given an array of student records, where the members of the record are the student name and their grade, how can you sort it by grade. The professor gave this example of what he called a 'Distributed Counting Sort'. I'm having trouble understanding it, and was hoping someone could give me the pseudocode or algorithm for the code below,
Thanks :)
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];
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这本质上是桶排序的变体。
这些是桶，每个桶对应一个可能的年级：
这会计算每个年级有多少学生。这告诉我们每个桶的大小：
这会将计数转换为累积计数。这为我们提供了目标数组中每个存储桶的结束位置。我相信
count[0]--位是为了解释基于 0 的数组。现在，它将每个学生放置在他/她的存储桶的末尾，并减少该存储桶的位置值。
这种排序的好处是它的时间复杂度为 O(n)，而不是 O(n*log(n))。然而，它仅适用于可以离散化为有限（且可管理）数量的存储桶的事物。
这段代码有点有趣的一点是，它颠倒了具有相同成绩的学生的顺序。您可以通过将累积计数更改为存储桶起始位置并在填充 NS 时递增它们来将其修改为稳定排序，或者更简单的是，在最后一个循环中向后遍历 S。
This is essentially a variation of Bucket Sort.
These are the buckets, one for each possible grade:
This counts how many students have each grade. This tells us the size of each bucket:
This converts the counts to be cumulative. This gives us the ending position of each bucket in the destination array. The
count[0]--bit is to account for 0 based arrays, I believe.Now it places each student at the end of his/her bucket, and decrements the position value for that bucket.
The nice thing about this kind of sort is that it's O(n), rather than O(n*log(n)). It only works for things that can be discretized into a finite (and manageable) number of buckets, however.
One thing that's a bit funny about this code is that it reverses the ordering of students that have the same grade. You could probably modify it to be a stable sort by changing the cumulative counts to be bucket starting positions and incrementing them when populating NS, or even easier, walk through S backwards in that last loop.
有 101 个等级，0 - 100
用每个等级的总分填充 count[]，例如 count[90]=4 表示有 4 人获得 90%
接下来，将这些总分转换为连续统计，即如果 57 人得分低于a 90，则 count[90] = 57 + 4，或 61。因此，对于每个 count[n]，您可以得到获得该成绩或更低成绩的人数。这对于最终数组很重要...最终数组中需要 61 个元素来容纳所有得分为 90 或更低的人。请注意， count[100] 应该 = n 传入。
count[0]-- 将整个计数向下移动 1，这会将基于 1 的最终数组转换为基于 0 的最终数组，例如，如果我有一个人得到一个零，count[0] = 1，所以我的最终数组将从 NS[1] 开始。我想从 NS[0] 开始。所以上面的 61 个元素现在是 60
最后（希望他不要再重复使用“i”），找到每个年级的位置...如果有 60 个人具有“90”或以下，则“90”年级属于第 60 位最终数组的元素 NS。这很令人困惑，部分原因是因为“--”...记住，“90”级有 60 个，因此您遇到的第一个“90”将被放置在 NS[60]，因为有 59 个等级较低的人。 “90”的计数减少到 59，因此下一个“90”将被放置在 NS[59] 处。等等。
最终结果是从最低等级到最高等级的数组，其中 NS[0] 是最低等级，NS[n] 是最高等级。
有道理吗？这真是一个美丽的算法！
There are 101 grades, 0 - 100
Fill count[] with the totals for each grade, e.g. count[90]=4 means four people got a 90%
Next, convert those totals to a running tally, i.e. if 57 people got lower than a 90, then count[90] = 57 + 4, or 61. So for each count[n], you have the number of people who got that grade or lower. This is important for the final array... you need 61 elements in the final array to hold everyone who got a 90 or lower. Note that count[100] should = n passed in.
count[0]-- is shifting the entire counts down by one, which converts a 1-based final array to a 0-based final array, e.g. if I have one person who got a zero, count[0] = 1, so my final array would start at NS[1]. I want to start at NS[0]. So the 61 elements above are now 60
Finally (wish he'd stop reusing 'i'), find the place for each grade... if there are 60 people with '90' or below, grade '90' belongs in the 60th element of the final array, NS. This is confusing, in part, because of the '--'... remember, there are 60 for grade '90', so the first '90' you come to will be placed at NS[60], because there are 59 people with lower grades. The count for '90' is decremented to 59, so the next '90' will be placed at NS[59]. And so forth.
The end result is a lowest-grade to highest-grade array, with NS[0] being the lowest grade, and NS[n] being the highest.
Make sense? It's really a beautiful algorithm!