排序考试的最佳算法
我是统计学课程的分级生,并以随机顺序给我一系列的纸质作业.我的部分工作是按字母顺序排列它们.我一直在使用类似于快速排序的方法,但其他评分者使用了不同的方法.我需要一种有效的排序方法,并且有正当理由,因为当我进行"大量"考试时,提供了理由.以下是我使用的一些细节:
- 我有一个名单,其中包含我应该看到的所有名称的按字母顺序排列的列表.
- 我不在乎让名字更像字母,而不仅仅是第一个字母.例如,如果"史密斯,约翰"出现在"Salk,Jonas"之前,我很好.
- 我将永远不会排序超过300个对象.
到目前为止,我的方法是查找班级名单中间的最后一个字母(即:如果有60篇论文,选择与第30个人相对应的姓氏字母),将其视为一个支点,并将所有字母放在上面一堆中位数,另一堆中的所有字母.如果一个字母与中位数相同,我将它放在中间桩中.我现在对上/下中位数桩做同样的事情.当堆足够小以至于堆栈中只有三个或四个字母时,我为每个字母创建一个堆栈,然后按字母顺序将堆栈折叠成主堆栈.
是否有专门为字母顺序设计的算法,或平均比我的方法更有效的东西？似乎没有问题的一种方法是为每个字母制作一个堆栈(26堆,最坏的情况),但这会消耗很多空间,以至于一个桌面不可行.
这是一个很好的问题！我们进行了一个小实验来接近答案。
我们的设置包括
3 个分拣机（A、B 和 C）。
3 堆 40 个学生问题集（每个分类器一个）。一套习题的页数从 1 到 5 不等。这些页是装订好的，并且在第一页的顶部写有学生的名字。
按字母顺序对堆栈进行排序的 3 种排序算法：
- 插入：从未排序的堆中取出最上面的项目并插入到已排序的堆中的正确位置。允许将已排序的堆散开。
- 桶：将每个项目分类到五个桶之一（AE、FJ、KO、PT、UZ）。然后使用插入排序对每个桶进行排序。合并已排序的桶。
- 合并：将物品分成 10 堆。使用插入排序对每一堆进行排序。将 10 堆排序成 5 对。通过反复查看该对的顶部项目并将按字母顺序排列的较高的项目放在该对结果堆的底部来合并每一对。将10堆合并为5堆后，将5堆中的2堆合并，这样就剩下4堆了。然后，重复成对合并，直到剩下一个排序好的堆。
测量：
- 排序算法完成之前的时间。
- 错放物品的数量（由其他分拣机测量）。
排序算法的顺序是随机的。
每一轮新的问题集堆栈都会在分类器之间交换并洗牌几分钟。
分拣机 A 和 B 各进行 9 轮，分拣机 C 进行 3 轮。
每个分拣员的桌子上都放了一张带有字母表和桶排序截止值的表。
这是我们设置的图片。
这是结果。
两个结论是直接的。
- 相对复杂的归并排序算法效果不佳。合并排序比在排序器桶/插入排序平均值内持续花费 57% 到 125% 的时间，并且没有明显的准确度提升。
我们推测，首先将问题集堆栈分成 10 堆的初始步骤可能会导致归并排序的结果乏善可陈。未来的研究人员可能会发现类似合并的算法与更有效的设置程序相结合是有效的。
- 尽管桶排序和插入排序都表现良好，但桶排序比排序器中的插入排序快 13% 到 25%。这种差异相当于为每个 40 个问题集排序节省了大约一分钟的时间。
我们推测，随着要排序的问题集数量超过 40 个，桶排序的相对效率会提高，并且插入排序将在 30 个或更少的堆栈中占主导地位，尽管需要更多的测试。桶排序和插入排序在准确率上没有明显差异。
最后，我们注意到我们的测试对象在分类能力方面存在重要的个体差异。分拣机 B 的平均性能始终优于分拣机 A 和 C，分别平均 39 秒和 101 秒。这表明，虽然采用的排序程序对排序速度很重要，但能力至少可以解释个体结果中的大部分差异。探索是什么让德国人如此出色的分拣机是未来研究的一个有前途的领域。
我浏览了一些网站，这些网站正在讨论供人类使用的算法，我看到的一个网站正在执行一种插入排序，即您将手头的一个直接放入正确的排序位置，将其放入一堆中。
这样做的低效率可能是因为随着堆变大，必须扫描堆才能找到位置，所以我认为要对此进行调整，您可以添加一个标签或充当索引的东西具体的字母位置。由于除了第一个字母之外您不关心字母顺序，因此这基本上会使您的插入成本为 O(1)
这只是我思考时的想法，所以我自己没有实际尝试过，也无法说如果堆足够大的话效果如何。但我认为它应该工作得相当好，因为标签可以让您立即访问要插入的位置。