Swift中sorted(by:)排序顺序不符合预期问题排查

问题根源：闭包不满足严格弱序要求 #

你的排序闭包return parents[rhs]!.contains(lhs)看似合理，但实际上违反了Swiftsorted方法强制要求的严格弱序规则，导致排序算法无法正确生成预期顺序。

严格弱序的核心要求之一是等价关系的传递性：如果a和b等价（既不a应该排在b前，也不b应该排在a前），b和c等价，那么a和c必须也等价。但你的闭包破坏了这一点：

• 比如21和2：互相不在对方的父列表中，属于等价关系
• 2和4：同样互相不在对方父列表中，属于等价关系
• 但21是4的父节点，21和4并不等价（21应该排在4前）

这种等价关系的断裂会让排序算法（如Timsort）失去可靠的排序依据，最终返回未定义的随机结果。

另外，你的闭包只处理了直接父子关系的比较，完全没有考虑间接依赖（比如21是5的父，5是4的父，21也应该排在4前），即使闭包满足严格弱序，也无法保证间接依赖的顺序正确。

正确解决方案：拓扑排序 #

你的需求本质是对**有向无环图（DAG）**进行拓扑排序——确保所有父节点排在子节点之前。普通的两两比较排序无法处理这类依赖关系，必须用专门的拓扑排序算法实现：

let parents: [Int: [Int]] = [2: [],
                             4: [5, 21],
                             5: [21],
                             6: [],
                             9: [],
                             10: [],
                             21: []]

// 构建父节点到子节点的映射，以及每个节点的入度（未排序的父节点数量）
var childrenMap: [Int: [Int]] = [:]
var inDegree: [Int: Int] = [:]

for (node, parentList) in parents {
    // 初始化当前节点的入度为父节点数量
    inDegree[node] = parentList.count
    // 给每个父节点添加当前节点作为子节点
    for parent in parentList {
        childrenMap[parent, default: []].append(node)
    }
}

// 初始化队列：所有没有父节点（入度为0）的节点
var queue = inDegree.filter { $0.value == 0 }.map { $0.key }
var sortedResult: [Int] = []

while !queue.isEmpty {
    let currentNode = queue.removeFirst()
    sortedResult.append(currentNode)
    
    // 遍历当前节点的所有子节点，将它们的入度减1
    for child in childrenMap[currentNode] ?? [] {
        inDegree[child]! -= 1
        // 当子节点入度为0时，说明所有父节点已排序，加入队列
        if inDegree[child]! == 0 {
            queue.append(child)
        }
    }
}

print(sortedResult)
// 输出示例：[2, 9, 6, 10, 21, 5, 4]（无依赖节点顺序可任意，核心依赖顺序21→5→4必满足）

算法逻辑说明： #

1. 构建映射：先把父节点到子节点的关系反向存储，同时记录每个节点需要等待多少个父节点排序完成（入度）。
2. 初始化队列：先把所有没有父节点的节点加入队列，这些节点可以直接放在结果里。
3. 迭代排序：每次从队列取出一个节点加入结果，然后把它的子节点的入度减1——当子节点的入度变为0，说明它的所有父节点都已排好序，就可以加入队列等待处理。

这种方法能确保所有直接和间接的父节点都排在子节点之前，完全满足你的需求。

内容的提问来源于stack exchange，提问作者Remco Poelstra