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

Question

下面的算法可以对三个变量x进行排序, y和 z类型 K使用 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);
}

在“最坏情况”下，这需要进行 3 次交换。然而，基础数学告诉我们，三个值的排序可以仅使用两次交换来完成。

示例:值 (c,b,a) 将使用三个交换进行排序:(c,b,a) -> (b,c,a) -> (b,a,c) -> (a ，公元前)。然而，一次交换就足够了:(c,b,a) -> (a,b,c)。

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

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 次比较，但只有两次交换。