我经常需要整理一副纸牌。这些是编号为 1 到 216 的“收藏家”卡片，并且有 double 和遗漏号码。
我正在寻找适用于实体卡片的排序算法。插入排序似乎很好，因为插入一张卡片不需要像在计算机内存中那样移动后续卡片。然而，扫描大甲板非常耗时。对于大牌组，您甚至有可能丢下牌组并不得不重新开始排序。
我可以在一张大 table 上画卡片，然后直接将每张卡片放在正确的位置，但这会占用相当多的空间，而且不是很方便。
我通常的方法是首先扫描整副牌，然后将它们堆叠 1-49、50-99、100-149、150-199、200+。然后我扫描每一副牌并将它们按 0、1、2、3、4 堆叠。最后，我对每 10 副牌应用插入排序。不过，这仍然是一个乏味的过程。
另一个想法是取 50 个堆栈并粗略地排序它们。 25 会在中间，40 会在堆栈末尾的某个地方，依此类推。这很快带来了大致排序的 50 副牌，我可以轻松地浏览它并修复排序。
我想知道是否可以将更复杂的算法方便地应用于物理甲板。我不明白我们如何应用快速排序和堆排序之类的东西需要知道牌组中卡片的索引。
最佳答案
我认为一种快速排序是最简单的方法。我想甚至有一些 Youtube 视频显示人们用普通的扑克牌这样做。
你翻过一副牌，把所有小于 100 的牌放在左边的一堆，大的放在右边的一堆。然后你递归遍历堆，深度优先(这样你就不会一次有太多堆)。在某个阈值(可能大约 5 张牌)，您只需对“手头”进行排序(可能类似于插入排序)。最后，您将这些堆堆放在一起。
您也可以进行归并排序:将一堆分成两堆，首先递归深度，直到得到两堆，每堆 5 张牌。将这两堆“放在手上”分类，然后将它们面朝上并排放置。通过始终将较低的显示卡放在结果堆中，将它们合并到结果堆中。您可以通过将那些堆正面朝上来查看哪些堆已经分类。确保始终合并大小相似的堆，否则继续拆分下一个未分类的堆。
编辑:基数排序也可能很好:将卡片按最后一位数字分成十堆，然后将这些堆按顺序堆叠在一起。然后，将卡片按倒数第二位分成十堆，再按顺序叠在一起。最后，将它们按倒数第三位数字(根据您的描述，即第一位数字)将它们堆叠在一起，然后将它们堆叠在一起，完成。毕竟，这可能是最简单的，而且它是 O(n)(您需要通过甲板三遍)。
关于algorithm - 对一副实际卡片进行排序的有效方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3324715/