设计一种高效的算法，在不到8次比较的情况下对5个不同的键进行排序

Question

设计一个高效的算法，在最坏的情况下，对5个不同的-非常大的-键进行排序，而不是8个比较。你不能使用基数排序。

Answer 1

比较A与B，C与D。WLOG，假设A>B和C>D。比较A与C。WLOG，假设A>C。将E排序为A-C-D。这可以通过两个比较来完成。将B排序为{E，C，D}。这可以通过两次比较来完成，总共有七次。

Answer 2

这是基于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)

Answer 3

它必须是7个或更多的比较。

有120种(5个阶乘)方法可以排列5个对象。使用6个比较的算法只能区分2^6 = 64个不同的初始排列，因此使用6个或更少比较的算法无法对所有可能的输入进行排序。

可能有一种仅使用7个比较进行排序的方法。如果您只想对5个元素进行排序，则可以通过暴力破解找到(或证明不存在)这样的算法。