人类对一堆卡片进行物理分类的最佳策略是什么？
What is the best strategy for a human to physically sort a pile of cards?
假设一个人有一堆实物牌。每张卡片都标有一个数字，并附有注释。作为一个实际示例，我有一堆 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]
我的问题是：给定这样的列表，人类执行的最佳算法是什么，可以对列表进行尽可能少的快速人类移动排序？通过快速的人类移动，可以想象卡片堆叠成 table，因此一个人可以将一张卡片从一堆移动到另一堆（最多可能同时堆的一个小的有限限制），或者将整个堆在另一个上面（因为这显然应该算作一个动作）。
假设
整理卡片的人有以下信息：
- 卡片上的值在 1 到 90 的范围内。
- 卡片数量大于90张，所以会出现重复
- 范围内的某些值可能缺失。
- 可使用的堆叠数。
91 层：每个值一层
最好的情况显然是在 table 上有足够的 space 用于未排序的堆栈加上与不同值一样多的堆栈。在这种情况下，每张牌都根据点数放入一叠，然后将 89 叠放在 90 叠的顶部，将 88 叠放在 89 叠的顶部，依此类推，直到有一个有序的叠。所需操作的数量等于卡片数量加上单独值的数量（示例中为 560 + 64）。
该人不知道该范围是否会缺少任何值，因此他只能在 91 堆栈有 space 时使用此策略。
33 叠或更少：有序子叠
如果没有足够的 space 用于 91 堆栈，可以使用以下策略：
- 拿起第一张卡并用它开始新的堆叠。
拿走以下每张牌，并且：
- 把它放在最上面一张牌等于或小于这张牌的第一堆上面。
- 如果卡片低于任何顶部卡片，则开始新的一叠
- 如果您 运行 从 space 中创建新的堆叠，通过重复从堆叠中取出最高的顶部卡片并将其放在有序堆叠的顶部，将堆叠合并到有序堆叠中.
- 再次开始拆分剩余的无序堆栈，这次以另一个方向对新堆栈进行排序，这样您最终得到的是顶部具有最低值的堆栈，可以将其与有序堆栈合并上一轮。
- 重复此操作，直到只剩下一叠。
对于示例数组，如果有 space 33 个堆栈（1 个输入堆栈、1 个有序堆栈、1 个用于合并堆栈的空位、30 个有序子堆栈），则此算法可以一次性完成).这将需要 560 + 560 个动作；这显然效率较低，因为所有卡片都必须一张一张地移动至少两次。
轮数取决于您是从向上排序还是向下排序开始；对于示例数组，向下似乎是最佳选择。输入未知，无法提前知道最佳选择；不过，差异永远不会超过 1 轮。
堆栈编号
上面提到的91个堆栈的方法可以适用于更少的堆栈。您将可用的 space 用于 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 - - - - - - - - -
更新：
不同大小的子范围
编号堆栈方法的更好版本是将无序堆栈拆分为子范围，然后将每个子范围拆分为编号堆栈并将它们添加到有序堆栈。每处理一个子范围，就会释放一个额外的堆栈 space，因此范围会变得越来越大。
在这个例子中，最高的牌被放在单独的牌堆上，较低的牌在范围内集中在一起，直到最低的牌是十一值范围 (1-11) 的一部分。 运行 该算法一次性所需的堆栈数是最大范围内的值数加一，因此在示例中为 12。
考虑到你的问题的原始版本，它要求对具有已知初始顺序的列表进行有效的排序方法，我利用堆栈中卡片的知识对示例进行了一些额外的优化:
- 不同值的数量：虽然卡片在 1-90 范围内，但只存在 65 个不同值。这减少了对 1-65 范围内的卡片进行排序的问题，并且没有丢失任何值。在示例中，为简单起见，我使用值 1-65。
- 相邻值的分离：有一些值，每张价值N的牌都在每张价值N+1的牌之前或之后。这用于 24/25 的情况，其中单张 25 张牌暂时放在 24 叠的顶部，而在 48/49 的情况下，使用单叠，因为牌已经在正确的顺序。
使用此方法，并了解初始顺序，具有 12 个堆栈 的 table 所需的操作数为 1158 个操作，这远低于有序子堆栈或编号堆栈方法所需的 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 个箱子并在一次通过中进行分类，但我认为这对人类来说很难处理。
假设一个人有一堆实物牌。每张卡片都标有一个数字，并附有注释。作为一个实际示例，我有一堆 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]
我的问题是：给定这样的列表，人类执行的最佳算法是什么，可以对列表进行尽可能少的快速人类移动排序？通过快速的人类移动，可以想象卡片堆叠成 table，因此一个人可以将一张卡片从一堆移动到另一堆（最多可能同时堆的一个小的有限限制），或者将整个堆在另一个上面（因为这显然应该算作一个动作）。
假设
整理卡片的人有以下信息：
- 卡片上的值在 1 到 90 的范围内。
- 卡片数量大于90张，所以会出现重复
- 范围内的某些值可能缺失。
- 可使用的堆叠数。
91 层：每个值一层
最好的情况显然是在 table 上有足够的 space 用于未排序的堆栈加上与不同值一样多的堆栈。在这种情况下，每张牌都根据点数放入一叠，然后将 89 叠放在 90 叠的顶部，将 88 叠放在 89 叠的顶部，依此类推，直到有一个有序的叠。所需操作的数量等于卡片数量加上单独值的数量（示例中为 560 + 64）。
该人不知道该范围是否会缺少任何值，因此他只能在 91 堆栈有 space 时使用此策略。
33 叠或更少：有序子叠
如果没有足够的 space 用于 91 堆栈，可以使用以下策略：
- 拿起第一张卡并用它开始新的堆叠。
拿走以下每张牌，并且：
- 把它放在最上面一张牌等于或小于这张牌的第一堆上面。
- 如果卡片低于任何顶部卡片，则开始新的一叠
- 如果您 运行 从 space 中创建新的堆叠，通过重复从堆叠中取出最高的顶部卡片并将其放在有序堆叠的顶部，将堆叠合并到有序堆叠中.
- 再次开始拆分剩余的无序堆栈，这次以另一个方向对新堆栈进行排序，这样您最终得到的是顶部具有最低值的堆栈，可以将其与有序堆栈合并上一轮。
- 重复此操作，直到只剩下一叠。
对于示例数组，如果有 space 33 个堆栈（1 个输入堆栈、1 个有序堆栈、1 个用于合并堆栈的空位、30 个有序子堆栈），则此算法可以一次性完成).这将需要 560 + 560 个动作；这显然效率较低，因为所有卡片都必须一张一张地移动至少两次。
轮数取决于您是从向上排序还是向下排序开始；对于示例数组，向下似乎是最佳选择。输入未知，无法提前知道最佳选择；不过，差异永远不会超过 1 轮。
堆栈编号
上面提到的91个堆栈的方法可以适用于更少的堆栈。您将可用的 space 用于 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 - - - - - - - - -
更新：
不同大小的子范围
编号堆栈方法的更好版本是将无序堆栈拆分为子范围，然后将每个子范围拆分为编号堆栈并将它们添加到有序堆栈。每处理一个子范围，就会释放一个额外的堆栈 space，因此范围会变得越来越大。
在这个例子中，最高的牌被放在单独的牌堆上，较低的牌在范围内集中在一起，直到最低的牌是十一值范围 (1-11) 的一部分。 运行 该算法一次性所需的堆栈数是最大范围内的值数加一，因此在示例中为 12。
考虑到你的问题的原始版本，它要求对具有已知初始顺序的列表进行有效的排序方法，我利用堆栈中卡片的知识对示例进行了一些额外的优化:
- 不同值的数量：虽然卡片在 1-90 范围内，但只存在 65 个不同值。这减少了对 1-65 范围内的卡片进行排序的问题，并且没有丢失任何值。在示例中，为简单起见，我使用值 1-65。
- 相邻值的分离：有一些值，每张价值N的牌都在每张价值N+1的牌之前或之后。这用于 24/25 的情况，其中单张 25 张牌暂时放在 24 叠的顶部，而在 48/49 的情况下，使用单叠，因为牌已经在正确的顺序。
使用此方法，并了解初始顺序，具有 12 个堆栈 的 table 所需的操作数为 1158 个操作，这远低于有序子堆栈或编号堆栈方法所需的 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 个箱子并在一次通过中进行分类，但我认为这对人类来说很难处理。