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

小编典典

algorithm

下面的算法可以排序三个变量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）。

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

阅读 313

2020-07-28

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

2020-07-28