如何三个变量使用最多两个互换排序？ [英] How to sort three variables using at most two swaps?

问题描述

下面的算法可以三个变量进行排序 X ，是和以Z K 可媲美使用运营商的LT; ：

The following algorithm can sort three variables x, y and z of type K which are comparable using 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);
}

这需要三个互换的最坏情况。然而基本数学告诉我们，可以仅使用两个互换来完成的三个值的排序。

This needs three swaps in the "worst case". However basic mathematics tells us, that the ordering of three values can be done using only two swaps.

例：值使用三个掉期（C，B，A）进行排序：（C，B，A） - >（B，C，A） - >（B，A，C） - >（一，公元前）。不过一个是swap就足够了。（C，B，A） - >（A，B，C）

Example: The values (c,b,a) will be sorted using three swaps: (c,b,a) -> (b,c,a) -> (b,a,c) -> (a,b,c). However one swap would have been enough: (c,b,a) -> (a,b,c).

什么是它在所有情况下排序三个变量与最多两个互换最简单的算法？

What would be the simplest algorithms which sorts three variables with at most two swaps in all cases?

推荐答案

查找最小的，这需要2比较，将其交换到第一位置。 再比较余下的2和交换，如果有必要的。

Find the smallest, this takes 2 comparisons, and swap it into the first position. Then compare the remaining 2 and swap if necessary.

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

This takes 3 comparisons, but only two swaps.

这篇关于如何三个变量使用最多两个互换排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！