用很少的比较对4号进行排序

Question

如何在5次比较中对4个数字进行排序？

Answer 1

将数字{a,b,c,d}分成2组{a,b} {c,d}.订购这两套中的每一套,你得到(e,f)(g,h).这是每组的一个比较.

现在从前面挑选最低(比较e,g).那是现在的三个比较.从(e,h)或(f,g)中选择下一个最低点.那是四个.比较最后两个元素(如果两个元素来自同一个集合,则可能甚至不需要此步骤,因此已经排序).这就是五点.

Answer 2

伪代码:

function sortFour(a,b,c,d)
    if a < b
        low1 = a
        high1 = b
    else 
        low1 = b
        high1 = a

    if c < d
        low2 = c
        high2 = d
    else
        low2 = d
        high2 = c

    if low1 < low2
        lowest = low1
        middle1 = low2
    else
        lowest = low2
        middle1 = low1

    if high1 > high2
        highest = high1
        middle2 = high2
    else
        highest = high2
        middle2 = high1

    if middle1 < middle2
        return (lowest,middle1,middle2,highest)
    else
        return (lowest,middle2,middle1,highest)

Answer 3

对于较少数量的输入，您可以生成最佳排序网络，以提供所需的最少比较次数。

您可以使用此页面轻松生成它们

按升序对四个数字进行排序：

if(num1>num2) swap(&num1,&num2);
if(num3>num4) swap(&num3,&num4);
if(num1>num3) swap(&num1,&num3);
if(num2>num4) swap(&num2,&num4);
if(num2>num3) swap(&num2,&num3);

在哪里

void swap(int *a,int *b)
{
   int temp = *a;
   *a = *b;
   *b = temp; 
}

或者您可以在没有额外变量的情况下实现自己的交换过程

（对于降序，只需将符号更改为 < ）

Answer 4

这不需要额外的内存或交换操作，每次排序只需 5 次比较

def sort4_descending(a,b,c,d):
if a > b:
    if b > c:
        if d > b:
            if d > a:
                return [d, a, b, c]
            else:
                return [a, d, b, c]
        else:
            if d > c:
                return [a, b, d, c]
            else:
                return [a, b, c, d]
    else:
        if a > c:
            if d > c:
                if d > a:
                    return [d, a, c, b]
                else:
                    return [a, d, c, b]
            else:
                if d > b:
                    return [a, c, d, b]
                else:
                    return [a, c, b, d]
        else:
            if d > a:
                if d > c:
                    return [d, c, a, b]
                else:
                    return [c, d, a, b]
            else:
                if d > b:
                    return [c, a, d, b]
                else:
                    return [c, a, b, d]
else:
    if a > c:
        if d > a:
            if d > b:
                return [d, b, a, c]
            else:
                return [b, d, a, c]
        else:
            if d > c:
                return [b, a, d, c]
            else:
                return [b, a, c, d]
    else:
        if b > c:
            if d > c:
                if d > b:
                    return [d, b, c, a]
                else:
                    return [b, d, c, a]
            else:
                if d > a:
                    return [b, c, d, a]
                else:
                    return [b, c, a, d]
        else:
            if d > b:
                if d > c:
                    return [d, c, b, a]
                else:
                    return [c, d, b, a]
            else:
                if d > a:
                    return [c, b, d, a]
                else:
                    return [c, b, a, d]