Java中对呈树状关联的自定义元组类列表进行排序的实现问题

问题核心原因 #

你之前自定义的compareTo方法不符合Java排序要求的全序比较规则：仅定义了直接相邻元组的比较逻辑，没有关联的非相邻元组全部返回0，排序算法会判定这类元组的顺序无需调整，因此无法得到期望的链式排序结果。

最优解决方案 #

结合你给出的前置约束（无环、唯一首尾节点、链式连续），不需要用排序方法，O(n)时间复杂度即可完成整理，同时支持Stream实现，无需递归：

实现步骤

• 构建「父ID -> 元组」的映射表，用于快速通过父ID查询对应元组
• 收集所有元组的子ID集合，用于查找根节点（父ID不在子ID集合中的元组即为首个元素）
• 从根节点开始，依次通过当前元组的子ID查询下一个元组，拼接得到完整有序列表

代码示例

假设你的自定义类DocumentIdVersionsStack已实现对应ID的getter方法，代码如下：

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.Stream;

// 你的元组类示例
class DocumentIdVersionsStack {
    private Long parentDocumentId;
    private Long childDocumentId;

    public Long getParentDocumentId() { return parentDocumentId; }
    public Long getChildDocumentId() { return childDocumentId; }
    // 省略构造方法等其他逻辑
}

public class TupleSort {
    public static void main(String[] args) {
        List<DocumentIdVersionsStack> list = // 你的原始无序列表
        
        // 1. 构建映射表和子ID集合
        Map<Long, DocumentIdVersionsStack> parentToTupleMap = list.stream()
                .collect(Collectors.toMap(DocumentIdVersionsStack::getParentDocumentId, Function.identity()));
        Set<Long> allChildIds = list.stream()
                .map(DocumentIdVersionsStack::getChildDocumentId)
                .collect(Collectors.toSet());
        
        // 2. 查找根元组
        DocumentIdVersionsStack root = list.stream()
                .filter(tuple -> !allChildIds.contains(tuple.getParentDocumentId()))
                .findFirst()
                .orElseThrow();
        
        // 3. Stream生成有序列表（Java 9+支持三参数iterate，Java 8可替换为下方简单循环实现）
        List<DocumentIdVersionsStack> sortedList = Stream.iterate(root, Objects::nonNull, tuple -> parentToTupleMap.get(tuple.getChildDocumentId()))
                .toList();
    }
}

如果是Java 8环境，第三步的Stream可以替换为如下写法，逻辑完全一致：

List<DocumentIdVersionsStack> sortedList = new ArrayList<>();
DocumentIdVersionsStack current = root;
while (current != null) {
    sortedList.add(current);
    current = parentToTupleMap.get(current.getChildDocumentId());
}

方案说明 #

• 完全无递归，代码逻辑简洁易维护
• 时间复杂度仅为O(n)，比基于比较的排序方法效率更高
• 完全匹配你给出的所有前置约束条件，稳定性高

内容的提问来源于stack exchange，提问作者Daniele Pavanelli