如何使用最多两次交换来排序三个变量？

Question

以下算法可以对类型为K的可比较变量x、y和z进行排序，使用的是operator<：

void sort2(K& x, K& y) {
   if(y < x)
      swap(x, y);
}      

void sort3(K& x, K& y, K& z) {
   sort2(x, y);
   sort2(y, z);
   sort2(x, y);
}

在“最坏情况”下，这需要三次交换。然而，基本数学告诉我们，只需使用两次交换即可对三个值进行排序。

例如：值(c,b,a)将使用三次交换进行排序：(c,b,a)->(b,c,a)->(b,a,c)->(a,b,c)。然而，只需要一次交换：(c,b,a)->(a,b,c)。

在所有情况下，用最多两次交换对三个变量排序的最简单算法是什么？

- Danvil

Answer 1

找到最小值，这需要2次比较，并将其交换到第一个位置。 然后比较剩下的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次比较，但只需要两次交换。

- deinst

---

这也许不是“最简单的算法” - 但它是唯一建议的算法。 - Danvil

Answer 2

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

2次交换，3次比较。

- healthy

Answer 3

2到3次比较，0到~1.7次交换

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

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);
            }
        }
    }
}

那么，它是如何工作的呢？基本上，它是一个未排序的插入排序：如果值已经排序（需要2次比较来检查），则算法不会交换任何内容。否则，它执行1或2个交换操作。但是，当需要2个交换操作时，算法会“旋转”值，以便执行4个移动而不是6个移动（除非进行了优化，否则交换操作应该花费3个移动）。

只有6种可能的3个值的排列方式。此算法执行所需的比较以知道我们正在处理哪个排列方式。然后进行交换并离开。因此，算法有6条可能的路径（包括数组已经排序的路径）。虽然它仍然易于阅读，但要等效地对4个值进行排序的算法将具有24个不同的路径，并且更难以阅读（对于n个值，有n！种可能的排列方式）。

既然我们已经进入了2015年，而且您似乎正在使用C++，我冒昧使用std::move来确保交换-旋转操作足够高效，并且即使对于可移动但不可复制的类型也能正常工作。

- Morwenn

Answer 4

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

这基本上是选择排序，最多执行n-1次交换。

- IVlad

Answer 5

如果您不在原地进行操作，可以在不进行任何交换的情况下执行它。

- gtrak

---

不，你可以直接把它们放在新数组的正确位置开始处理 :-)，只是挑剔一下，这相当于交换，但并不真正交换。 - gtrak

好的，我想到了其他的事情 ;) - Danvil

Answer 6

最近我也遇到了一个类似的问题——高效地排序三个值。你在问题中关注了交换操作，但如果你想要提高性能，应该关注比较操作和分支！当对这样一个“微小”的数组进行排序时，一个好的想法是考虑使用额外的存储空间，这对于如此少量的值是合适的。我想出了一种类似于专门的“归并排序”的方法（见下面的代码）。

正如tenfour所建议的那样，我查看了汇编代码，下面的代码编译成了一组紧凑的内联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
}

- Angel Sinigersky

Answer 7

在表格中编码一个排序网络。我提供的维基百科文章应该会帮助你在需要弄清楚在其他情况下（即更大的数组）应该将什么放入表格时提供参考。

- anon

Answer 8

我认为你想要的是在每一步中找到最优的交换而不仅仅是一个有效的交换。为了做到这一点，只需找到列表中一个元素和后面一个元素之间的最大差异，并进行交换。在一个三元组中，有三种可能的交换，1-3、1-2 和 2-3。在每一步中找到这三个交换中的最大差异并执行该操作。我很确定这会在三个元素的最坏情况下给出两个交换。只有在交换相对于比较元素来说相对昂贵时才真正有意义，否则可能不值得提前进行额外的分析。

- bshields

Answer 9

很酷的问题 :)

如果您可以使用汇编语言，并且值适合寄存器，那么您可能可以通过将它们加载到寄存器中并执行几次比较，跳转到正确的情况以将值放回来，从而非常快地完成它。也许您的编译器已经进行了这种优化。

无论如何，如果性能是您的目标，请查看生成的机器代码并在那里进行优化。对于这样一个小算法，那就是您可以挤出性能的地方。

- tenfour

Answer 10

这可以用一个真值表来说明，该表涉及到每个可能的比较组合，以查看我们如何最优化你在此提到的交换。

数值 | 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

通过这种方式提出问题，我们可以很容易地看出，通过最初检查和交换第1个和第3个元素，交换后我们可以在第一个元素中获得的最小值可以是x或y。这简化了之后的if检查，因此我们可以在x>y时交换第1个和第2个元素，或在y>z时交换第2个和第3个元素。

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

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

不需要任何嵌套的if条件语句。最多只需要2-3个简单的比较来完成2次交换。

- SimplyAPL