如何使用最多两个交换对三个变量进行排序?

找到最小的,这需要两个比较,并将其交换到第一个位置。 然后比较其余2个,必要时进行交换。

if (x < y) {
   if (z < x) swap(x,z);
} else {
  if (y < z) swap(x,y);
  else swap(x,z);
} 
if(z<y) swap(y,z);

这需要3个比较,但只有两个交换。

void sort(int& a, int& b, int& c)
{
   swap(a, min(a, min(b, c)));
   swap(b, min(b, c));
}

2次交换,3次比较。

2到3个比较,0到1.7个交换

旧问题,新答案…以下算法排序 x , y 和 z 根据它们的值和0到1.7的交换操作进行2到3次比较。

void sort3(K& x, K& y, K& z)
{    
    if (y < x) {
        if (z < x) {
            if (z < y) {
                swap(x, z);
            } else {
                K tmp = std::move(x);
                x = std::move(y);
                y = std::move(z);
                z = std::move(tmp);
            }
        } else {
            swap(x, y);
        }
    } else {
        if (z < y) {
            if (z < x) {
                K tmp = std::move(z);
                z = std::move(y);
                y = std::move(x);
                x = std::move(tmp);
            } else {
                swap(y, z);
            }
        }
    }
}

那么,它是如何工作的呢?它基本上是一个展开的插入排序:如果值已经排序(需要两个比较来检查),那么算法就不会交换任何内容。否则,它执行1或2个交换操作。但是,当需要2次交换操作时,算法_旋转_值,以便执行4次移动而不是6次(交换操作应花费3次移动, unless optimized )

只有6种可能的3值排列。这个算法进行必要的比较,以了解我们正在处理的排列。然后交换离开。因此,该算法有6个可能的路径(包括因为数组已经排序而不执行任何操作的路径)。虽然它仍然是人类可读的,但对4个值进行排序的等效优化算法将有24个不同的路径,并且更难读取(对于n个值,有n个!可能的排列)。

既然我们已经2015了,你好像在使用C++,我自由使用。 std::move 因此,为了确保交换旋转thingy足够有效,即使对于可移动但不可复制的类型也可以工作。

找到最小值并将其与第一个值交换。找到第二个最小值并将其与第二个值交换。最多两次交换。

这基本上是 selection sort ,最多只能执行 n - 1 掉期交易。

如果你没有在适当的地方做,你可以在没有任何交换的情况下执行它。

编码A sorting network 在桌子上。我链接的wikipedia文章应该可以帮助您提供参考资料,以防您需要在其他情况下(即更大的数组)找出放在表中的内容。

我认为你想要的是在每个步骤中找到最佳的交换,而不仅仅是一个有效的交换。要做到这一点,只需在列表的后面找到元素和元素之间最大的区别,并交换它们。在三元组中,有三种可能的交换:1-3、1-2和2-3。在每一步中,找出这三种交换之间的最大差异,并做到这一点。很肯定,在3个元素的最坏情况下,这给出了两个交换。只有当交换相对比较元素比较昂贵时才真正有意义,否则可能不值得预先进行额外的分析。

好问题:)

如果程序集对您可用,并且值适合一个寄存器,那么您可以非常快速地将它们加载到寄存器中并进行一些比较,跳到正确的场景中将值放回。也许编译器已经进行了优化。

不管怎样,如果性能是您的目标,请查看生成的机器代码并在那里进行优化。对于这样一个小的算法,您可以从中挤出性能。

我最近不得不解决一个类似的问题——高效地对三个值进行排序。在您的问题中,您专注于交换操作。如果您正在寻找性能,请集中精力比较操作和分支!当用三个值对这样一个“微小”的数组进行排序时,一个好主意是考虑使用额外的存储,这对于如此少的值是合适的。我想出了一个专门的“合并排序”(见下面的代码)。

正如 TEN4 建议,我查看了程序集,下面的代码编译成一组紧凑的内联CPU寄存器操作,速度非常快。附加变量“arr12”也存储在CPU寄存器中。排序需要两个或三个比较操作。可以很容易地将函数转换为模板(此处不作说明)。

inline void sort3_descending( double * arr )
{
    double  arr12[ 2 ];

    // sort first two values
    if( arr[ 0 ] > arr[ 1 ] )
    {
        arr12[ 0 ] = arr[ 0 ];
        arr12[ 1 ] = arr[ 1 ];
    } // if
    else
    {
        arr12[ 0 ] = arr[ 1 ];
        arr12[ 1 ] = arr[ 0 ];
    } // else

    // decide where to put arr12 and the third original value arr[ 3 ]
    if( arr12[ 1 ] > arr[ 2 ] )
    {
        arr[ 0 ] = arr12[ 0 ];
        arr[ 1 ] = arr12[ 1 ];
    } // if
    else if( arr[ 2 ] > arr12[ 0 ] )
    {
        arr[ 0 ] = arr  [ 2 ];
        arr[ 1 ] = arr12[ 0 ];
        arr[ 2 ] = arr12[ 1 ];
    } // if
    else
    {
        arr[ 0 ] = arr12[ 0 ];
        arr[ 1 ] = arr  [ 2 ];
        arr[ 2 ] = arr12[ 1 ];
    } // else
}

这可以用一个与每种可能的比较组合相关的真值表来说明,以了解我们如何最好地优化您在这里提到的交换。

值X<Y Y<Z X<Z

X,Y,Z_Y_Y_Y

X,Z,Y_Y_N_Y

Y,X,Z N Y Y

Y,Z,X N Y N

Z,X,Y_Y_N_N

Z,Y,X N N N

通过这种方式构建问题,我们可以很容易地看到,通过最初检查和交换第一个和第三个元素,交换后第一个元素中的最小值可以是x或y。这简化了之后的if检查,以便我们可以在x>y时交换第一个和第二个元素,或者交换第二个和第三个元素wh。EN和G.

if (x > z) {
    swap(x,z);
}

if (x > y) {
    swap(x,y);
} else if (y > z) {
    swap(y,z);
}

不需要任何嵌套的if条件。仅2-3个简单比较,最多2个交换。