排序考试的最佳算法

我是一名统计学课程的分级员，并按随机顺序给我一系列的纸张家庭作业分配。我的部分工作是按字母顺序排列它们。我一直在使用类似于快速分类的方法，但其他分级人员使用了不同的方法。我想要一个高效的排序方法，说明理由，因为当我有考试的“大”号，说明理由提供。这里有一些细节我已经利用：排序考试的最佳算法

我有一个包含一个按字母顺序列出名册我应该看到的所有名字。
我不介意让名字比第一个字母更符合字母顺序。例如，如果“史密斯，约翰”出现在“索尔克，乔纳斯”之前，我很好。
我永远不会排序超过300个对象。

我的方法迄今已发现的中位数最后一个字母（例如：如果有60篇论文，挑相当于30人的姓氏字母）类名册，把它作为一个支点，并把所有的字母都放在一个中间位置，并把所有的字母放在另一个中。如果一封信和中位数一样，我把它放在中间的一堆。我现在在上/中位数桩上做同样的事情。当堆足够小以至于堆栈中只有三个或四个字母时，我为每个字母组成一个堆栈，然后按字母顺序将堆栈折叠成主堆栈。

是否有任何专门为字母排序而设计的算法，或者是比我的方法更高效的算法？一种看起来没有问题的方法是为每封信（26堆，最坏的情况）制作一个堆栈，但这会消耗太多的空间，以至于无法在一张桌子上使用。

来源

2012-03-16 Christopher Aden

这种愚蠢的情况形式化的原因，更多源于与另一位研究生的友好争论，他们使用两个桩的插入排序（创建一个排序的桩，将每个纸张从未排序的桩中按顺序添加到排序的桩中）比从一个严重的需要。我希望SO社区可以为另一种特定方法提供理由。 – 2012-03-16 18:25:28

我四处张望着一些正在讨论人类使用算法的网站，而我看到的一个网站正在进行一种插入排序，在那里你把一个直接放在那里正确的排序应该是。

这种效率低下可能是由于不得不扫描整个堆来找到位置，因为堆越来越大，所以我在考虑为此进行调整，您可以添加一个标签或其他可以充当一个特定字母位置的索引。既然你不关心第一个字母以外的字母顺序，这基本上会把你的插入成本设置为O（1）

这只是一个想到它的想法，所以我没有尝试过它本人，并且无法说明如何使用足够大的桩有效。但我认为它应该工作得很好，因为这些标签会让您立即访问您想要插入的位置。

来源

2012-03-16 21:12:11 MysticXG

快速排序可能不是最好的，因为它的效率取决于数据的选择。无论如何，只有300次考试，我会做的是创建26堆（每个字母一个），只需一次通过所有考试将它们放入适当的桩

来源

2012-03-16 16:53:47 scibuff

我没有看到作为枢轴功能的效率。因为我有一个班级名单，但是，我确切地知道我在我的项目中有哪些元素，所以我认为这允许我选择数据透视表。中点值是否具有最佳效率？ – 2012-03-16 18:18:21

您的最后一段是插入排序。如果26堆是两个很多，使用24 :)。如果26堆太多，将字母和考试分成5堆。然后对每一堆进行分类，再次有5个案例（6个）。

来源

2012-03-16 16:54:45 mpez0

从查看可视化来看，插入排序似乎比快速排序更糟糕。对于大多数未排序的堆栈来说，它似乎并不是最节省时间的。 – 2012-03-16 18:22:46

我使用桶排序。使用四个桶，再次使用另一个4桶排序对每个桶进行排序，通过强力排序每个子桶（1/16）！

来源

2013-08-29 17:34:15 Parsa

排序第一个字母为M桩
，一旦你需要> = M桩：把所有物品不匹配在第一次运行结束的垃圾桩
开始信在M桩完成
递归，用剩菜从垃圾一堆

常量M可以调整，以匹配你的能力到m atch &第一眼看到多个字母。（和可用的桌面空间）

在实践中，您将不需要超过几次运行，合理值为M。（Zipf /帕累托定律）

来源

2013-08-29 17:53:39 wildplasser

我基于我的算法的前提是，需要我确定两个元素的正确顺序的时间并不一致。例如，我很容易说A在D之前，但是需要我来判断Q是否在T之前，反之亦然（一般来说，字母越接近字母的末尾，彼此之间，更可能的是我必须精神上背诵字母表以确保）。

鉴于此，我觉得它减少了繁琐的字母，背诵，如果我把测试变成字母 “块”：

开始（AF ISH）
前中期（GK ISH）
Late Middle（LP ish）
End（QZ ish）。（a）这是我在决定字母顺序时最差的部门，（b）其中一些字母不常开始姓氏

存在重叠 - 即有时候我会觉得Q是Late Middle，有时候我会觉得它是End。这种情况取决于那时候桩的大小以及我最后排序的字母......我的理论是，通过不在头脑中拼出字母表而节省的时间大于后来排序的额外时间上。

但是，就我所知。除了最初的组块，我永远无法决定什么是最有效的......

来源

2014-11-04 02:07:34 user1476176

这是一个很好的问题！我们进行了一个小实验来接近答案。

我们的设置包括了

3分拣机（A，B和C）。
3堆40学生问题集（每个分拣机一个）。问题集的张数在1到5之间。这些纸张已装订并在第一页的顶部写有学生名字。
3种排序算法到堆栈按字母顺序排序：
- 插入：从无序桩径顶部项目，并插入到在排序桩正确的位置。允许分拣堆垛扇出。
- 存储桶：将每个项目分为五个存储桶（A-E，F-J，K-O，P-T，U-Z）之一。然后使用插入排序对每个桶进行排序组合已分类的桶。
- 合并：将项目分成10堆。使用插入排序对每堆进行排序。把10堆分成5对。通过反复观察对中的顶部项目并将字母顺序较高的一个放在对的最后一堆的底部来合并每一对。将10个桩合并成5个桩后，合并5个桩中的2个，以便剩下4个桩。然后，反复合并，直到剩下一个排序的桩。
三围：
- 时间，直到排序算法完成。
- 错放物品的数量（由其他分拣机测量）。
排序算法的顺序是随机的。
每个新一轮的问题集堆栈在分拣机之间进行交换并且洗牌几分钟。
分拣机A和B各做了9轮，分拣机C做了3轮。
在每个分拣机的桌子上放上一张带有字母表和水桶分类截止的纸张。