c - 最小-最大选择——那是什么算法？

Question

我试图了解这段代码中发生了什么 -> http://wiki.tiker.net/MedianFilter
我感兴趣的部分是一种从给定列表中同时选择最小值和最大值的算法。它(即下面的每个 mnmx*)改变了列表顺序，所以我们得到一个"new"列表，其中最小值在最左边，最大值在最右边。让我引用相关部分:

#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() 按顺序对它们中的每一个产生一个新排序的列表，最小值在最左边，最大值在最右边？

Answer 1

回答您的问题，这是 Divide and Conquer 的天真实现，其中除法是恒定长度。

可以通过动态划分列表(例如，列表的一半)，递归调用每一半，然后重新组合列表，同时修改候选列表的最大值和最小值(the从递归调用返回的每个子列表的第一个和最后一个元素)。