假设有一个物理一堆卡片。每张卡片上都标有一个数字，并附有注释。作为一个实际的例子，我有一摞560张牌，按照这个顺序:
[36, 32, 30, 21, 73, 90, 9, 24, 81, 27, 65, 15, 53, 82, 28, 43, 45, 21, 41, 69, 38, 39, 6, 17, 67, 20, 54, 37, 65, 18, 38, 14, 68, 73, 30, 4, 13, 39, 3, 14, 36, 68, 18, 4, 82, 43, 1, 18, 41, 71, 24, 70, 1, 4, 23, 39, 20, 28, 30, 37, 39, 41, 49, 79, 43, 22, 55, 70, 3, 22, 28, 82, 3, 12, 70, 24, 54, 78, 19, 49, 41, 27, 41, 67, 10, 23, 24, 20, 27, 44, 80, 70, 41, 6, 21, 20, 48, 73, 54, 1, 7, 67, 38, 26, 66, 30, 43, 36, 55, 16, 24, 27, 28, 43, 28, 1, 3, 9, 38, 19, 88, 65, 68, 21, 44, 36, 6, 39, 67, 6, 69, 49, 56, 39, 49, 41, 50, 18, 82, 17, 22, 47, 68, 18, 24, 53, 51, 68, 53, 65, 1, 7, 7, 38, 55, 55, 16, 67, 82, 78, 70, 1, 20, 30, 54, 73, 78, 82, 20, 20, 22, 27, 30, 32, 65, 78, 44, 9, 12, 31, 3, 70, 24, 4, 54, 3, 28, 39, 49, 55, 66, 69, 70, 9, 21, 24, 54, 71, 13, 6, 67, 38, 22, 50, 36, 30, 1, 12, 9, 24, 44, 48, 54, 78, 3, 21, 32, 56, 66, 68, 70, 82, 80, 10, 28, 28, 29, 41, 43, 43, 45, 43, 74, 55, 2, 50, 74, 38, 67, 27, 51, 67, 38, 36, 11, 70, 41, 6, 65, 39, 49, 4, 17, 41, 27, 6, 10, 56, 82, 55, 66, 73, 78, 73, 55, 70, 3, 68, 67, 20, 54, 15, 25, 43, 49, 54, 68, 79, 69, 24, 55, 78, 37, 74, 73, 3, 67, 30, 65, 18, 53, 31, 38, 39, 38, 2, 16, 39, 6, 67, 80, 20, 66, 14, 27, 9, 36, 47, 21, 41, 1, 24, 54, 56, 11, 70, 1, 19, 4, 17, 30, 36, 38, 38, 44, 67, 36, 19, 65, 27, 30, 15, 36, 21, 41, 69, 9, 38, 65, 68, 21, 36, 14, 17, 68, 18, 24, 44, 74, 73, 54, 1, 1, 31, 49, 24, 55, 78, 73, 3, 10, 68, 73, 30, 7, 23, 82, 43, 2, 70, 27, 54, 80, 68, 73, 30, 47, 79, 51, 38, 39, 6, 67, 20, 54, 67, 6, 39, 13, 49, 41, 27, 56, 66, 18, 24, 6, 9, 67, 65, 27, 82, 20, 78, 25, 23, 50, 81, 20, 27, 70, 47, 41, 6, 24, 28, 43, 28, 51, 70, 1, 39, 78, 68, 10, 74, 21, 20, 3, 73, 54, 30, 2, 78, 9, 73, 37, 47, 21, 30, 65, 79, 23, 18, 37, 20, 53, 41, 67, 6, 4, 18, 39, 49, 41, 57, 28, 8, 55, 48, 1, 39, 20, 7, 27, 70, 41, 30, 20, 41, 16, 67, 6, 39, 25, 8, 49, 18, 82, 19, 55, 12, 70, 8, 55, 44, 3, 65, 11, 2, 3, 54, 9, 78, 22, 71, 50, 39, 49, 18, 22, 13, 82, 55, 36, 29, 15, 27, 28, 28, 49, 39, 9, 18, 9, 78, 68, 44, 21, 20, 3, 50, 29, 7, 82, 20, 78, 66, 32, 30, 43, 82, 43, 1, 23, 49, 24, 55, 37, 9, 22, 38, 65, 68, 20, 21, 36, 12, 18, 41, 43, 14, 28, 82, 3, 6, 25, 81, 21, 41]
我的问题是:给定这样的列表，人类执行的最佳算法是什么?它将对列表进行排序，使人类快速移动的数量最少?通过快速移动，人们可以想象卡片堆叠在一张桌子上，因此一个人可以将一张卡片从一堆卡片移动到另一张卡片上(最多可能同时摞的有限限制)，或者将整个卡片放在另一堆卡片上(因为这显然应该算作一次移动)。
假设
整理卡片的人有以下信息:
- 卡片上的数值范围为1 ~ 90。
- 卡片的数量大于90，所以会有重复。
- 范围内的某些值可能缺失。
- 可以使用的栈数。
91个栈:每个值一个栈
最好的情况显然是在表上有足够的空间来容纳未排序的堆栈以及有不同值的堆栈。在这种情况下，每张牌都按值放在一摞牌上，之后第89摞放在第90摞的上面，第88摞放在第89摞的上面，以此类推，直到有一个有序的摞。所需操作的数量等于纸牌的数量加上独立值的数量(在本例中为560 + 64)。
这个人不知道范围内是否会有任何值丢失，所以他只能在有91个堆栈的空间时使用这种策略。
33栈或以下:有序子栈
如果没有足够的空间容纳91个堆栈，可以使用以下策略:
- 取第一张卡片并使用它开始一个新的堆栈。
-
取以下每张卡片，
- 将其放在第一个堆栈的顶部，该堆栈的顶部卡片等于或低于该卡。
对于示例数组，如果有33个堆栈(1个输入堆栈，1个有序堆栈，1个用于合并堆栈的空位置，30个有序子堆栈)的空间，则该算法可以一次完成。这需要560 + 560个操作;这显然效率较低，因为所有的牌都必须一张一张地移动至少两次。
轮数取决于你是向上还是向下排序;对于示例数组，向下似乎是最好的选择。在输入未知的情况下，无法提前知道最佳选择;不过，两者的差别永远不会超过1轮。
编号栈
上面提到的91个堆栈的方法可以适用于更少的堆栈。您使用子堆栈的可用空间来存储N个最大值，并将较低的值放在无序堆栈上。当所有的卡都被移动后，将编号的子堆栈堆叠起来，并以无序堆栈作为输入堆栈重新开始。每轮你寻找N个更小的值，直到你完成整个范围。与前一种方法相比，这种方法的优点是子堆栈是按堆栈移动的，而不是按单个卡片移动。结果更好，除了33到39的范围。
这是每堆总数量的回合数和动作:
| ORDERED SUB-STACKS (UP FIRST / DOWN FIRST) | NUMBERED STACKS
stacks | rounds actions per card | rounds actions per card
91 1 1 1120 1120 2.0 2.0 1 624 1.1
...
48 1 1 1120 1120 2.0 2.0 2 973 1.7
...
40 1 1 1120 1120 2.0 2.0 3 1111 2.0
39 1 1 1120 1120 2.0 2.0 3 1125 2.0
38 1 1 1120 1120 2.0 2.0 3 1159 2.1
37 1 1 1120 1120 2.0 2.0 3 1207 2.2
36 1 1 1120 1120 2.0 2.0 3 1226 2.2
35 2 1 1674 1120 3.0 2.0 3 1247 2.2
34 2 1 1635 1120 2.9 2.0 3 1263 2.3
33 2 1 1559 1120 2.8 2.0 3 1280 2.3
32 2 2 1521 1644 2.7 2.9 4 1318 2.4
31 2 2 1512 1627 2.7 2.9 4 1344 2.4
30 2 2 1504 1607 2.7 2.9 4 1368 2.4
29 2 2 1458 1518 2.6 2.7 4 1408 2.5
28 3 2 1945 1499 3.5 2.7 4 1455 2.6
27 3 2 1923 1473 3.4 2.6 4 1501 2.7
26 3 3 1905 1999 3.4 3.6 4 1560 2.8
25 3 3 1883 1979 3.4 3.5 5 1629 2.9
24 3 3 1822 1899 3.3 3.4 5 1697 3.0
23 4 3 2255 1802 4.0 3.2 5 1788 3.2
22 4 4 2206 2286 3.9 4.1 5 1854 3.3
21 4 4 2070 2197 3.7 3.9 5 1880 3.4
20 5 5 2441 2512 4.4 4.5 6 2037 3.6
19 6 5 2876 2410 5.1 4.3 6 2165 3.9
18 6 5 2659 2313 4.7 4.1 6 2247 4.0
17 7 7 3021 2804 5.4 5.0 7 2350 4.2
16 7 8 2926 3071 5.2 5.5 7 2500 4.5
15 8 9 3302 3546 5.9 6.3 8 2680 4.8
14 12 11 4686 4363 8.4 7.8 9 2930 5.2
13 14 13 5241 4729 9.4 8.4 9 3187 5.7
12 16 17 5481 5826 9.8 10.4 10 3458 6.2
11 19 18 6262 5985 11.2 10.7 12 3900 7.0
10 24 23 7679 7421 13.7 13.3 13 4385 7.8
9 32 33 10477 10719 18.7 19.1 15 5038 9.0
8 41 40 12187 12130 21.8 21.7 18 6030 10.8
7 54 55 16464 16488 29.4 29.4 23 7427 13.3
6 82 83 25293 25326 45.2 45.2 30 9784 17.5
5 150 151 42225 42230 75.4 75.4 45 14529 25.9
4 334 335 93301 93305 166.6 166.6 89 28717 51.3
3 - - - - - - - - -
更新:
变化大小的子范围
编号堆栈方法的更好版本是将无序堆栈拆分为子范围，然后将每个子范围拆分为编号堆栈，并将它们添加到有序堆栈中。每处理一个子范围，就会释放一个额外的堆栈空间，因此范围可以变得越来越大。
在这个例子中，最高的牌被放在单独的堆栈中，较低的牌被集中在一起，直到最低的牌是11个值范围(1-11)的一部分。一次运行此算法所需的堆栈数是最大范围内的值数加上1，因此在示例中为12。
考虑到你的问题的原始版本，它要求对具有已知初始顺序的列表进行有效的排序方法，我已经使用堆栈中卡片的知识对示例进行了一些额外的优化:
- 不同值个数虽然卡片的范围是1-90，但只有65个不同的值存在。这将问题简化为排序1-65范围内的卡片，并且没有丢失值。在本例中，为了简单起见，我使用了1-65的值。
- 相邻值的分离:有几个值，每个值为N的牌出现在每个值为N+1的牌之前或之后。这是在24/25的情况下使用的，其中单个25张牌暂时放在24张牌的顶部，并且在48/49的情况下，使用单个堆栈，因为卡片已经处于正确的顺序。
使用此方法，并知道初始顺序，对于具有12堆栈的表所需的操作数量is1158个动作，这比有序子堆栈或编号堆栈方法所需的5826个操作(或33个堆栈)和3458个操作(或38个堆栈)要低得多。
下面的图表显示了12摞中每张牌的值或值的范围。每一行都显示了算法中的一个步骤，在右边的列中，您可以找到达到该步骤所需的操作数量。
1 2 3 4 5 6 7 8 9 10 11 12
ACTIONS
1-65
65 64 63 62-59 58-54 53-47 46-40 39-32 31-22 21-12 11-1 560
65-63 62-59 58-54 53-47 46-40 39-32 31-22 21-12 11-1 2
65-62 61 60 59 58-54 53-47 46-40 39-32 31-22 21-12 11-1 25
65-59 58-54 53-47 46-40 39-32 31-22 21-12 11-1 3
65-58 57 56 55 54 53-47 46-40 39-32 31-22 21-12 11-1 42
65-54 53-47 46-40 39-32 31-22 21-12 11-1 4
65-53 52 51 50 49-48 47 46-40 39-32 31-22 21-12 11-1 73
65-47 46-40 39-32 31-22 21-12 11-1 5
65-46 45 44 43 42 41 40 39-32 31-22 21-12 11-1 52
65-40 39-32 31-22 21-12 11-1 6
65-39 38 37 36 35 34 33 32 31-22 21-12 11-1 96
65-32 31-22 21-12 11-1 7
65-31 30 29 28 27 26 24+25 23 22 21-12 11-1 82
65-22 21-12 11-1 8+1
65-21 20 19 18 17 16 15 14 13 12 11-1 82
65-12 11-1 9
65-11 10 9 8 7 6 5 4 3 2 1 91
65- 1 10
----
1158
一般来说，对于未知的初始排序，12个堆栈将排序N张牌，最多有66个不同的值(11 + 10 + 9 +…)+ 1)，动作数为N + (N - #66) + 10 + 9 + 8 + ... + 1，其中#66是值最高的卡牌数(因为这些牌不需要移动两次)。
1 2 3 4 5 6 7 8 9 10 11 12 <-STACKS
ACTIONS
1-66
66 65-64 63-61 60-57 56-52 51-46 45-39 38-31 30-22 21-12 11-1 N
66-65 64 63-61 60-57 56-52 51-46 45-39 38-31 30-22 21-12 11-1 #65-64
66-64 63-61 60-57 56-52 51-46 45-39 38-31 30-22 21-12 11-1 1
66-63 62 61 60-57 56-52 51-46 45-39 38-31 30-22 21-12 11-1 #63-61
66-61 60-57 56-52 51-46 45-39 38-31 30-22 21-12 11-1 2
66-60 59 58 57 56-52 51-46 45-39 38-31 30-22 21-12 11-1 #60-57
66-57 56-52 51-46 45-39 38-31 30-22 21-12 11-1 3
66-56 55 54 53 52 51-46 45-39 38-31 30-22 21-12 11-1 #56-52
66-52 51-46 45-39 38-31 30-22 21-12 11-1 4
66-51 50 49 48 47 46 45-39 38-31 30-22 21-12 11-1 #51-46
66-46 45-39 38-31 30-22 21-12 11-1 5
66-45 44 43 42 41 40 39 38-31 30-22 21-12 11-1 #45-39
66-39 38-31 30-22 21-12 11-1 6
66-38 37 36 35 34 33 32 31 30-22 21-12 11-1 #38-31
66-31 30-22 21-12 11-1 7
66-30 29 28 27 26 25 24 23 22 21-12 11-1 #30-22
66-22 21-12 11-1 8
66-21 20 19 18 17 16 15 14 13 12 11-1 #21-12
66-12 11-1 9
66-11 10 9 8 7 6 5 4 3 2 1 #11- 1
66- 1 10
我建议使用最低有效位数到最高有效位数的桶排序，基本上模拟卡片排序器。有10个箱子，编号为0到9，用来放置卡片，还有一个输入的卡片堆要排序，正面朝上。该人从输入堆栈的顶部取出一张卡片，并将其面朝下放入与最低有效数字相对应的箱子中。一旦所有的卡片都被放入箱子里，箱子里的10摞卡片就会从箱子里拿出来，从箱子9开始，到箱子0结束，正面朝上堆叠。这个过程再次重复，这次使用最高有效数字，在第二次传递之后，卡片被排序(并且该方法是稳定的，保留相等卡片的顺序)。
在真正的卡片分拣机上，所有的卡片都是面朝下放置的，所以操作员从0到9的箱子中取出卡片，将它们面朝下放置回卡片分拣机的输入托盘中。
一次处理90个箱子并进行排序是可能的，但我认为这对人类来说很难处理。