Eri*_*his 22 sorting algorithm
我经常要排序卡片.这些是"收集器"卡,编号从1到216,有双打和缺少数字.
我正在寻找适用于物理卡的排序算法.插入排序似乎很好,因为插入卡不需要像计算机内存中那样移动后续卡.但是,通过大型平台进行扫描非常耗时.有了一个大甲板,甚至有可能你可以放下甲板,不得不重新开始排序.
我可以将卡片放在一张大桌子上并直接将每张卡片放在正确的位置,但这需要相当大的空间并且不太方便.
我通常的方法是在甲板上进行第一次扫描并将它们放入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)(你需要三次通过牌组).