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

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

在“最坏情况”下，这需要进行三个交换。但是基本数学告诉我们，三个值的排序只能使用两个交换来完成。

示例：将使用三个交换对值（c，b，a）进行排序：（c，b，a）->（b，c，a）->（b，a，c）->（a，b，
C）。但是一次交换就足够了：（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次比较，但只有两次交换。