如何基于返回中间值的三元比较器实现列表排序？

由于效率并非首要考量，推荐使用选择排序或插入排序，两者逻辑简单，容易基于给定的Evaluator实现，以下是具体思路：

一、选择排序（推荐，逻辑更直观） #

核心思路是每次从未排序区间中找到最小元素，将其放到已排序区间的末尾，重复此过程直到所有元素有序。

实现步骤： #

1. 处理边界情况：
   • 若数组长度 ≤ 1，直接返回；
   • 若数组长度为 2，由于无法调用middleOf（需三个不同元素），可直接返回两元素的任意顺序（或根据业务场景补充逻辑）。
2. 初始化已排序区间：
   • 首次从未排序区间（整个数组）中找出最小元素：
     1. 取任意三个元素a, b, c，调用evaluator.middleOf(a, b, c)得到中间元素的索引mid；
     2. 剩余两个元素x, y中，任选一个与另外两个元素（含中间元素）再次调用middleOf，结合结果确定x和y的相对大小，从而找出三个元素中的最小者；
     3. 将此最小元素与数组中其他元素逐一比较（借助任意第三个元素作为参考），最终确定整个数组的最小元素，将其移到数组开头，作为已排序区间的第一个元素。
3. 迭代找最小元素：
   • 对于剩余的未排序区间，以已排序区间的第一个元素（全局最小）作为参考，每次取当前候选最小元素、待比较元素、全局最小元素调用middleOf：
     • 若返回值为2（全局最小是中间），说明候选最小和待比较元素都比全局最小大，此时返回值为0或1对应的元素就是两者中的较小者，更新候选最小；
     • 若返回值为0或1，直接确定较小的元素，更新候选最小。
   • 将找到的未排序区间最小元素移到已排序区间的末尾。
4. 重复步骤3，直到未排序区间为空。

二、插入排序 #

核心思路是维护一个已排序的子数组，每次将未排序的元素插入到已排序子数组的正确位置。

实现步骤： #

1. 初始化已排序子数组：将数组第一个元素作为初始已排序子数组。
2. 逐个插入元素：
   • 遍历数组中剩余的每个元素curr：
     1. 遍历已排序子数组，每次取两个相邻元素s_left和s_right：
        • 调用evaluator.middleOf(curr, s_left, s_right)：
          • 若返回0：curr是中间元素，直接将curr插入到s_left和s_right之间；
          • 若返回1：s_left是中间元素，说明curr和s_right分别在s_left两侧，结合已排序子数组的顺序（s_left < s_right），可判断curr < s_left，将curr插入到s_left左侧；
          • 若返回2：s_right是中间元素，同理判断curr > s_right，将curr插入到s_right右侧。
     2. 若curr比已排序子数组所有元素都小，插入到最左侧；若都大，插入到最右侧。
3. 重复步骤2，直到所有元素插入完成。

三、关键工具：模拟二元比较（可选） #

如果想直接使用基于二元比较的排序算法（如冒泡排序），可以用Evaluator模拟出二元比较的结果（确定a < b或a > b）：

1. 对于两个不同元素a和b，找到任意第三个元素c（数组长度≥3）；
2. 调用int midIdx = evaluator.middleOf(a, b, c)：
   • 若midIdx == 1：b是中间元素，说明a和c分别在b两侧，此时再调用evaluator.middleOf(a, c, b)，结合已排序的参考元素（如全局最小），即可确定a和b的相对大小；
   • 若midIdx == 0或midIdx == 2，同理推导a和b的顺序。

内容的提问来源于stack exchange，提问作者Erlich Bachman