使用黑盒比较器对列表进行排序

Question

Given 是唯一对象的列表和评估器的实例。求值器可以比较三个元素并返回三个元素中的“中间”。它必须恰好是三个，并且不能在相同的对象之间进行比较。

当您只能比较三个一组的元素并知道哪一个位于其他两个（中间的）之间时，如何对这个列表进行排序？

既然效率不是主要问题，那么什么算法可以解决这个问题呢？我想到了一种强力的左右指针方式，但这对我来说效果不太好。除此之外，我可以想到一种插入排序，也许还有带有枢轴元素的快速排序（尽管可靠的枢轴和分区不容易配置）

public interface Evaluator {

    /*
    Compare three items.
    Will return 0, 1 or 2, if respectively x0, x1 or x2 is the middle element of the three provided.
    Comparing equal elements is undefined.
     */
    int middleOf(Dish x0, Dish x1, Dish x2);
}

Answer 1

最简单的想法是引入一个虚拟值作为第三个元素来比较两个元素。

作为虚拟元素，我会选择域的最大可能值，我们称之为 MAX

以下是如何使用它：

您想知道两个（不同）元素 A 或 B 中哪一个更大

伪代码

 int compare(Dish A, Dish B){
   // if A equals B is possible add handling here
   middle=getMiddle(A,B,X);
   if(A==middle)
     return 1;
   else 
     return -1
 }