最小-最大选择 - 这是什么算法？

Question

我正在尝试理解这段代码的含义 -> http://wiki.tiker.net/MedianFilter
我感兴趣的部分是同时从给定列表中选择最小值和最大值的算法。它（即下面的每个mnmx*）改变了列表的顺序，使我们得到一个“新”列表，其最小值在最左边，最大值在最右边。让我引用相关部分：

#define s2(a,b)            { float tmp = a; a = min(a,b); b = max(tmp,b); }
#define mn3(a,b,c)         s2(a,b); s2(a,c);
#define mx3(a,b,c)         s2(b,c); s2(a,c);

#define mnmx3(a,b,c)       mx3(a,b,c); s2(a,b);                               // 3     exchanges
#define mnmx4(a,b,c,d)     s2(a,b); s2(c,d); s2(a,c); s2(b,d);                // 4 exchanges
#define mnmx5(a,b,c,d,e)   s2(a,b); s2(c,d); mn3(a,c,e); mx3(b,d,e);          // 6 exchanges
#define mnmx6(a,b,c,d,e,f) s2(a,d); s2(b,e); s2(c,f); mn3(a,b,c); mx3(d,e,f); // 7 exchanges

我能看到这个可行，但我真的不知道如何将其概括为给定长度的列表。它是某些众所周知的方法的特殊情况吗？有什么想法吗？

编辑：重新表达问题：每个mnmx*都由排序对值((a,b),(c,d),...(x,z))的有序列表给出，计算mnmx*意味着计算s2(a,b)，s2(c,d)，...，s2(x,z)。现在，对于给定的n，如何找到最短的mnmx，即最短的排序对有序列表，使得按顺序在每个列表上计算s2()将产生一个新的排序列表，其中最小值位于最左侧，最大值位于最右侧？

- tms

---

我所能想到的宏在这些情况下唯一的优点就是类型通用性（适用于所有类型），但这在开始时用float tmp = a来代替而失去了。有更好的方法可以通过更易读的代码实现同样的事情。 - amit

我相信 mnmx3，...，mnmx6 可以实现最小值和最大值的操作，尽管说实话，我只检查了 mnmx6。我正在寻找一种方法来制作给定 k 的 mnmxk。 - tms

是的，它似乎也适用于3、4、5。 - tms

所以你只是在谈论 mnmx* 函数；明白了。在问题中澄清这一点可能会有所帮助。 - Patrick87

这些宏让我想起了怪异艾尔·扬科维克（Weird Al Yankovic）的歌曲《Mr. Popeil》中的一句话：“你甚至可以用它切割罐头。但你不会想这么做！” </sarcasm> - Mike Holt

Answer 1

回答你的问题，这是一种分而治之的天真实现，其中划分是以恒定长度为基础的。

可以通过动态地划分列表（例如，将列表分成一半），对每个子列表进行递归调用，然后在修改候选项的最大值和最小值的同时重新组合列表，从而将其扩展为动态长度。候选项是从递归调用返回的每个子列表的第一个和最后一个元素。

- amit

---

好的，那可能已经足够接近了。还有一件事情对我很有趣。每个 mnmx* 都由一个有序的索引对列表给出，即要计算 s2() 的次数以及在哪些值上进行计算。现在，显然对于给定的输入长度，这样的有序列表中有一个最短的（即 mnmx 中最短的）。虽然进行“朴素分治”是可以的，但我不确定它是否等同于“以最少的方式计算 s2()（对于给定的长度），以产生所需的结果”。 - tms