如何以ListA为模板对ListB排序？现有Comparator实现有误

现有两个列表：

• 模板列表listA：

List<Integer> listA = Arrays.asList(1,2,3,4,5,6,7,6,5,4,3,2,1,0);

• 待排序列表listB：

List<Integer> listB = Arrays.asList(0,106,107,101,105,102,102,103,104,106,105,103,101,104);

期望得到的排序后列表listC顺序为：[101,102,103,104,106,107,106,105,104,103,102,101,0]

错误实现及结果 #

以下是尝试用Comparator实现的代码，但未得到正确结果：

public class JavaComparators {
    public static void main(String[] args) {
        
        List<Integer> listA = Arrays.asList(1,2,3,4,5,6,7,6,5,4,3,2,1,0);
        List<Integer> listB = Arrays.asList(0,106,107,101,105,102,102,103,104,106,105,103,101,104);
        
        System.err.println(listA);
        System.err.println(listB);

        // Create a set of elements present in listB for faster lookup
        Set<Integer> setB = new HashSet<>(listB);

        // Sort listA based on the index in listB or use a default index if not present
        listB.sort(Comparator.comparingInt(a -> {
            int index = listA.indexOf(a);
            
            if (index == -1) {
                // If the element is not in listB, check for nearby values
                int indexPlusOne = listA.indexOf(a + 100);
                int indexMinusOne = listA.indexOf(a - 100);

                if (indexPlusOne != -1) {
                    return indexPlusOne;
                } else if (indexMinusOne != -1) {
                    return indexMinusOne;
                } else {
                    // Use a default index if not present in listB or nearby
                    return Integer.MAX_VALUE;
                }
            }

            return index;
        }));

        System.err.println("Rearranged listB: " + listB);
    }
}

运行得到错误结果：

[1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 1, 0]
[0, 106, 107, 101, 105, 102, 102, 103, 104, 106, 105, 103, 101, 104]
Rearranged listB: [101, 101, 102, 102, 103, 103, 104, 104, 105, 105, 106, 106, 107, 0]

错误原因分析 #

原代码的Comparator逻辑是将所有对应模板中同一值的元素归为一组排序，比如所有101（对应listA的1）都会被放在一起，而没有遵循listA中1出现的先后位置（先在开头，后在倒数第二位）来依次选取元素，导致结果是同类型元素扎堆，不符合期望的顺序。

正确实现方式 #

正确思路是：先建立listB元素到模板listA对应值的映射，再按listA的顺序依次从对应映射的元素集合中取出元素，组装成结果列表。

代码实现：

import java.util.*;

public class TemplateSort {
    public static void main(String[] args) {
        List<Integer> listA = Arrays.asList(1,2,3,4,5,6,7,6,5,4,3,2,1,0);
        List<Integer> listB = Arrays.asList(0,106,107,101,105,102,102,103,104,106,105,103,101,104);

        // 建立映射：模板值 -> 对应的listB元素队列
        Map<Integer, Queue<Integer>> valueMap = new HashMap<>();
        for (Integer num : listB) {
            int key;
            if (num == 0) {
                key = 0;
            } else {
                key = num - 100; // 101对应1，102对应2...
            }
            valueMap.computeIfAbsent(key, k -> new LinkedList<>()).offer(num);
        }

        // 按listA的顺序组装结果
        List<Integer> listC = new ArrayList<>();
        for (Integer templateVal : listA) {
            Queue<Integer> queue = valueMap.get(templateVal);
            if (queue != null && !queue.isEmpty()) {
                listC.add(queue.poll());
            }
        }

        System.out.println("期望结果：[101,102,103,104,106,107,106,105,104,103,102,101,0]");
        System.out.println("实际结果：" + listC);
    }
}

代码说明 #

1. 映射构建：遍历listB，将每个元素转换为对应的模板值（比如101转成1），并把元素存入对应模板值的队列中，保证元素的原始顺序。
2. 结果组装：遍历listA的每个模板值，从对应队列中取出一个元素添加到结果列表，这样完全遵循listA的顺序，同时消耗listB中的元素。

运行结果：

期望结果：[101,102,103,104,106,107,106,105,104,103,102,101,0]
实际结果：[101, 102, 103, 104, 106, 107, 106, 105, 104, 103, 102, 101, 0]

内容的提问来源于stack exchange，提问作者Kapil Panchal