对大量测试成绩进行排序

Question

您有一个很大的测试分数列表（例如 N > 10000），您想要对其进行排序。测试分数在 1 到 100 之间。对列表进行排序的最快方法是什么？

第一个想法。我们有一个 O(N log N) 界限，但我们还有关于数组中数量的附加信息，所以我认为我们可以做得更好。

第二个想法：我们应该使用哈希表吗？我们关心重复项吗？无法看到如何使用哈希表。

第三个想法：这与基数排序有关系吗？不知道。

第四个想法：我们是否可以通过创建另一个列表来对这个列表进行排序，然后通过原始计数元素出现的频率。但是我们是否需要另一遍来创建更大的排序列表，这将是 O(N^2)。即太大。

这是一个非常简单的问题还是一个非常困难的问题？

Answer 1

这是一个非常简单的问题，假设所有分数都是整数。

这是最简单的算法。我们将发起 count, ，一个包含 100 个零的整数数组。对于每个分数 s, ，我们将添加 1 count[s]. 。为了产生想要的排序分数，我们将输出 count[1] 1秒， count[2] 2秒，...，最后 count[100] 100 秒。

这种排序算法称为计数排序。

案例超过 $N>10000$ 1 到 100 之间的测试分数是计数排序的主要用途。时间复杂度为 $O(N)$ 并且空间复杂度受 100 的某个小常数倍的限制。

您可能想检查 计数排序 了解更多信息。

Answer 2

是，使用像合并排序的排序算法，我们可以通过O（n * logn）来实现这一目标，我们可以在这里做得更好。 考虑到测试分数的界限的附加信息在这里非常有用。

我们关心重复吗？

如果我们正在处理得分，并且不关心student_name或subject_info等其他信息，我们只需要按照scorded格式的分数，U可以使用此算法。

     maintain a int table[101] = {0}   - hash table with key as score
                        //all elements are initialised to 0

    array contains all scores
    for score in array
         table[score] = table[score] +1
         //above in O(N) time and O(1) space.

    sorted_list = {} // initially empty
    for (score= 0; score < 101;i++)
      for(count = 0; count < table[i]; count++)
          sorted_list.add(score)
          //the above runs in O(N) time and O(N) space.

.

现在，如果我们关心信息，如果学生/拍摄的分数，它属于它使用以下方法。 我假设您将以C / C ++结构或任何对象格式存储分数和相关信息。

现在维护大小100的哈希表（测试分数范围） 键=分数 value=具有此分数的对象或实例列表（如果您是 分类为学生列表，然后是使用此分数的学生列表）

如果您熟悉C / C ++，则可以使用链接列表数组来实现此数据结构。这里使用的散列技术是单独的散列。

数据结构功能是这样的 DS [得分]对链接列表有指针/引用 使用另一个哈希映射来识别DS中每个子列表的尾部，我们可以在O（1）时间内插入新元素。

所以在一个从i= 0到i的单一通行证中 插入后

我们可以创建一个新列表，其中我们创建了单个传递DS。

算法是这样的。

让array包含具有它们各自的分数

的所有对象

    for (i = 0; i< n; i++)
      key = array[i].score
      DS[key].insert(array[i]) //the tail part can be used for O(1) insertion.

     //the above loop runs in O(N)

     sorted_list = {} // empty_list
     for(score = 1; score<=100;score++)
       for each (obj in DS[score]) 
          sorted_list.add(obj)

      //the above loop runs in O(N).

     //the N refers to the size of original list here.

.

此方法神奇地是基于队列的基数100.阅读更多关于Radix排序和使用队列实现的计数排序。

从问题： “第四次思想：我们可以通过创建另一个列表来排序此列表，然后通过原始计数频率发生的元素。但是我们需要另一个传球来创建一个更大的排序列表，这将是O（n ^ 2）。即太大了。“

我认为你错过了另一个通行证会改变n到n2。除非您将“另一个通行证”放在循环中，否则它不会。

我希望我回答你的所有问题。