如何使用最多两次掉期对三个变量进行排序？

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

Answer 2

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

2次交换,3次比较.

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

那么它是怎样工作的？它是basiccaly一个展开的插入排序:如果值已经排序(需要2次比较来检查),那么算法不会交换任何东西.否则,它执行1或2次交换操作.但是,当需要2个交换操作时,算法"旋转"这些值,而不是执行4次移动(交换操作应该花费3次移动,除非进行优化).

3个值只有6种可能的排列.该算法进行比较以了解我们正在处理哪种排列.然后它进行交换和离开.因此,该算法有6条可能的路径(包括它没有做任何路径的路径,因为数组已经被排序).虽然它仍然是人类可读的,但是对4个值进行排序的等效最优算法将具有24个不同的路径并且将更难以读取(对于n个值,存在n个可能的排列).

由于我们已经在2015年并且您似乎正在使用C++,因此我采取了自由使用std::move,以确保swap-rotate thingy足够高效并且甚至可以用于可移动但不可复制的类型.

Answer 4

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

这基本上是选择排序,它将在大多数n - 1交换中执行.