设计一种有效的算法来排序5个不同的 - 非常大的 - 密钥,在最坏的情况下少于8个比较.你不能使用基数排序.
比较A到B和C到D. WLOG,假设A> B和C> D. 比较A到C. WLOG,假设A> C. 将E排序为ACD.这可以通过两次比较来完成.将B排序为{E,C,D}.这可以通过两次比较来完成,总共七次.
这是基于Beta答案的伪代码.因为我匆忙做了这件事,可能会有一些错误.
if (A > B)
swap A, B
if (C > D)
swap C, D
if (A > C)
swap A, C
swap B, D # Thanks Deqing!
if (E > C)
if (E > D) %A C D E
if (B > D)
if (B > E)
return (A, C, D, E, B)
else
return (A, C, D, B, E)
else
if (B < C)
return (A, B, C, D, E)
else
return (A, C, B, D, E)
else %A C E D
if (B > E)
if (B > D)
return (A, C, E, D, B)
else
return (A, C, E, B, D)
else
if (B < C)
return (A, B, C, E, D)
else
return (A, C, B, E, D)
else
if (E < A) % E A C D
if (B > C)
if (B > D)
return (E, A, C, D, B)
else
return (E, A, C, B, D)
else
return (E, A, B, C, D)
else %A E C D
if (B > C)
if (B > D)
return (A, E, C, D, B)
else
return (A, E, C, B, D)
else
if (B < E)
return (A, B, E, C, D)
else
return (A, E, B, C, D)
由于log 2(5!)= 6.9,因此可以在最差的投射中对五个项目进行七次比较进行排序.我建议检查是否有任何标准排序算法达到这个数字 - 如果不是这样,由于所需的比较数量较少,因此很难对比较序列进行硬编码.
我建议编写一个程序来查找比较序列.创建一个包含数字1到5的所有120种排列的列表.然后尝试所有十个可能的比较并选择那个,在两个相同大小的列表中尽可能好地分割列表.执行此拆分并以递归方式将相同的过程应用于两个列表.
我写了一个小程序来完成这个,这就是结果.
Comparison 1: 0-1 [60|60] // First comparison item 0 with item 1, splits case 60/60 Comparison 2: 2-3 [30|30] // Second comparison for the first half of the first comparison Comparison 3: 0-2 [15|15] // Third comparison for the first half of the second comparison for the first half of first comparison Comparison 4: 2-4 [8|7] Comparison 5: 3-4 [4|4] Comparison 6: 1-3 [2|2] Comparison 7: 1-2 [1|1] Comparison 7: 1-4 [1|1] Comparison 6: 1-4 [2|2] Comparison 7: 1-2 [1|1] Comparison 7: 1-3 [1|1] Comparison 5: 0-4 [4|3] Comparison 6: 1-2 [2|2] Comparison 7: 1-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 6: 1-2 [1|2] Comparison 7: 1-3 [1|1] Comparison 4: 0-4 [8|7] Comparison 5: 1-4 [4|4] Comparison 6: 1-3 [2|2] Comparison 7: 3-4 [1|1] Comparison 7: 0-3 [1|1] Comparison 6: 3-4 [2|2] Comparison 7: 0-3 [1|1] Comparison 7: 1-3 [1|1] Comparison 5: 0-3 [4|3] Comparison 6: 1-3 [2|2] Comparison 7: 2-4 [1|1] Comparison 7: 2-4 [1|1] Comparison 6: 2-4 [2|1] Comparison 7: 3-4 [1|1] Comparison 3: 0-3 [15|15] // Third comparison for the second half of the second comparison for the first half of first comparison Comparison 4: 3-4 [8|7] Comparison 5: 2-4 [4|4] Comparison 6: 1-2 [2|2] Comparison 7: 1-3 [1|1] Comparison 7: 1-4 [1|1] Comparison 6: 1-4 [2|2] Comparison 7: 1-3 [1|1] Comparison 7: 1-2 [1|1] Comparison 5: 0-4 [4|3] Comparison 6: 1-3 [2|2] Comparison 7: 1-4 [1|1] Comparison 7: 1-2 [1|1] Comparison 6: 1-2 [2|1] Comparison 7: 1-3 [1|1] Comparison 4: 0-4 [8|7] Comparison 5: 1-4 [4|4] Comparison 6: 1-2 [2|2] Comparison 7: 2-4 [1|1] Comparison 7: 0-2 [1|1] Comparison 6: 2-4 [2|2] Comparison 7: 0-2 [1|1] Comparison 7: 1-2 [1|1] Comparison 5: 0-2 [4|3] Comparison 6: 1-2 [2|2] Comparison 7: 3-4 [1|1] Comparison 7: 3-4 [1|1] Comparison 6: 2-4 [1|2] Comparison 7: 3-4 [1|1] Comparison 2: 2-3 [30|30] // Second comparison for the second half of the first comparison Comparison 3: 0-3 [15|15] Comparison 4: 0-4 [7|8] Comparison 5: 0-2 [3|4] Comparison 6: 2-4 [2|1] Comparison 7: 3-4 [1|1] Comparison 6: 1-2 [2|2] Comparison 7: 3-4 [1|1] Comparison 7: 3-4 [1|1] Comparison 5: 1-4 [4|4] Comparison 6: 2-4 [2|2] Comparison 7: 1-2 [1|1] Comparison 7: 0-2 [1|1] Comparison 6: 1-2 [2|2] Comparison 7: 0-2 [1|1] Comparison 7: 2-4 [1|1] Comparison 4: 3-4 [7|8] Comparison 5: 0-4 [3|4] Comparison 6: 1-2 [1|2] Comparison 7: 1-3 [1|1] Comparison 6: 1-3 [2|2] Comparison 7: 1-2 [1|1] Comparison 7: 1-4 [1|1] Comparison 5: 2-4 [4|4] Comparison 6: 1-4 [2|2] Comparison 7: 1-2 [1|1] Comparison 7: 1-3 [1|1] Comparison 6: 1-2 [2|2] Comparison 7: 1-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 3: 0-2 [15|15] Comparison 4: 0-4 [7|8] Comparison 5: 0-3 [3|4] Comparison 6: 2-4 [1|2] Comparison 7: 3-4 [1|1] Comparison 6: 1-3 [2|2] Comparison 7: 2-4 [1|1] Comparison 7: 2-4 [1|1] Comparison 5: 1-4 [4|4] Comparison 6: 3-4 [2|2] Comparison 7: 1-3 [1|1] Comparison 7: 0-3 [1|1] Comparison 6: 1-3 [2|2] Comparison 7: 0-3 [1|1] Comparison 7: 3-4 [1|1] Comparison 4: 2-4 [7|8] Comparison 5: 0-4 [3|4] Comparison 6: 1-2 [2|1] Comparison 7: 1-3 [1|1] Comparison 6: 1-2 [2|2] Comparison 7: 1-3 [1|1] Comparison 7: 1-4 [1|1] Comparison 5: 3-4 [4|4] Comparison 6: 1-4 [2|2] Comparison 7: 1-3 [1|1] Comparison 7: 1-2 [1|1] Comparison 6: 1-3 [2|2] Comparison 7: 1-4 [1|1] Comparison 7: 1-2 [1|1]
但现在问题是如何以有效的方式实现这一点.也许可以使用查找表来存储比较序列.我也不确定如何以有效的方式从这个比较序列中导出有序输出.
通过比较从上面对结果进行排序揭示了第一次比较的明显结构,但随着比较数量的增加,它变得更难.所有块都围绕中间对称-----.
Comparison 1: 0-1 [60|60] Comparison 2: 2-3 [30|30] Comparison 2: 2-3 [30|30] Comparison 3: 0-2 [15|15] Comparison 3: 0-3 [15|15] ----- Comparison 3: 0-3 [15|15] Comparison 3: 0-2 [15|15] Comparison 4: 2-4 [8|7] Comparison 4: 0-4 [8|7] Comparison 4: 3-4 [8|7] Comparison 4: 0-4 [8|7] ----- Comparison 4: 0-4 [7|8] Comparison 4: 3-4 [7|8] Comparison 4: 0-4 [7|8] Comparison 4: 2-4 [7|8] Comparison 5: 3-4 [4|4] Comparison 5: 0-4 [4|3] Comparison 5: 1-4 [4|4] Comparison 5: 0-3 [4|3] Comparison 5: 2-4 [4|4] Comparison 5: 0-4 [4|3] Comparison 5: 1-4 [4|4] Comparison 5: 0-2 [4|3] ----- Comparison 5: 0-2 [3|4] Comparison 5: 1-4 [4|4] Comparison 5: 0-4 [3|4] Comparison 5: 2-4 [4|4] Comparison 5: 0-3 [3|4] Comparison 5: 1-4 [4|4] Comparison 5: 0-4 [3|4] Comparison 5: 3-4 [4|4] Comparison 6: 1-3 [2|2] Comparison 6: 1-4 [2|2] Comparison 6: 1-2 [2|2] Comparison 6: 1-2 [1|2] Comparison 6: 1-3 [2|2] Comparison 6: 3-4 [2|2] Comparison 6: 1-3 [2|2] Comparison 6: 2-4 [2|1] Comparison 6: 1-2 [2|2] Comparison 6: 1-4 [2|2] Comparison 6: 1-3 [2|2] Comparison 6: 1-2 [2|1] Comparison 6: 1-2 [2|2] Comparison 6: 2-4 [2|2] Comparison 6: 1-2 [2|2] Comparison 6: 2-4 [1|2] ----- Comparison 6: 2-4 [2|1] Comparison 6: 1-2 [2|2] Comparison 6: 2-4 [2|2] Comparison 6: 1-2 [2|2] Comparison 6: 1-2 [1|2] Comparison 6: 1-3 [2|2] Comparison 6: 1-2 [2|2] Comparison 6: 1-4 [2|2] Comparison 6: 2-4 [1|2] Comparison 6: 1-3 [2|2] Comparison 6: 3-4 [2|2] Comparison 6: 1-3 [2|2] Comparison 6: 1-2 [2|1] Comparison 6: 1-2 [2|2] Comparison 6: 1-4 [2|2] Comparison 6: 1-3 [2|2] Comparison 7: 1-2 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 0-3 [1|1] Comparison 7: 0-3 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 2-4 [1|1] Comparison 7: 2-4 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 2-4 [1|1] Comparison 7: 0-2 [1|1] Comparison 7: 0-2 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 3-4 [1|1] ----- Comparison 7: 3-4 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 0-2 [1|1] Comparison 7: 0-2 [1|1] Comparison 7: 2-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 2-4 [1|1] Comparison 7: 2-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 0-3 [1|1] Comparison 7: 0-3 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-2 [1|1]
它必须是7次或更多次比较.
有5个物体的120(5个因子)方式被安排.使用6次比较的算法只能区分2 ^ 6 = 64种不同的初始排列,因此使用6次或更少比较的算法无法对所有可能的输入进行排序.
可能有一种方法只使用7次比较进行排序.如果您只想对5个元素进行排序,那么可以通过强力发现(或证明不存在)这样的算法.
京公网安备 11010802040832号 | 京ICP备19059560号-6 