Java 比较器不比较每个 object

Question

我在使用 Java Comparator 时遇到了一些问题。所以我有一个 parent 节点，它有一个列表 children。我想对那些 children 进行排序，表面上看起来很简单，但是当 Comparator 进行排序时，它只检查某些 objects 与某些 objects，然后我假设它推断objects的位置，比如a在[=18=之前]，f在[=18=之后]，b在[之前=18=] 表示 b 在 f.

之前

下面是我当前设置的示例。我有一个 parent 节点 a 和 4 children 个节点 b、e、l、g。当我对这些 children 进行排序时，我希望顺序为 b、g、l、e，因此按字母排序并始终确保parent 节点在前。

（画的不好请见谅）

很简单，我有一个Nodeclass，它包含一个ID，所以它是字母然后是children的列表。

public class Node {

    private char id;
    private Node parent;
    private List<Node> children = new ArrayList<>();


    public Node(char id) {
        this.id = id;
    }

    public void addChild(Node child) {
        this.children.add(child);
    }

    public List<Node> getChildren() {
        return children;
    }

    public char getId() {
        return id;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    public Node getParent() {
        return parent;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

    @Override
    public boolean equals(Object obj) {
        return ((Node) obj).getId() == this.id;
    }
}

然后我有 NodeComparator class，它首先检查节点是否是您的 children，然后如果是您先行，反之亦然，然后按字母顺序排列。

    @Override
    public int compare(Node o1, Node o2) {
        if (o1.getChildren().contains(o2)) {
            return -1;
        }

        if (o2.getChildren().contains(o1)) {
            return 1;
        }

        String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

        int firstNodeIndex = -10;
        int secondNodeIndex = -10;
        for (int i = 0; i < alphabet.length(); i++) {
            if (alphabet.charAt(i) == o1.getId()) {
                firstNodeIndex = i;
            }
            if (alphabet.charAt(i) == o2.getId()) {
                secondNodeIndex = i;
            }
        }
        if (firstNodeIndex > secondNodeIndex) {
            return 1;
        } else if (firstNodeIndex == secondNodeIndex) {
            return 0;
        }else {
            return -1;
        }
    }
}

问题是排序完成后会检查：

E against B
G against E
L against G

所以它从不检查 L 与 E，因此它无法知道哪个应该先出现。

Answer 1

您的订单违反了Comparator的合同：

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

compare('G','E') > 0 // since 'G' comes after 'E' in the alphabet

和

compare('E','L') > 0 // since 'E' is a child of 'L'

但是

compare('G','L') < 0 // since 'G' comes before 'L' in the alphabet

由于您的 Comparator 不是有效的 Comparator，它可能会产生异常或意外结果。

Answer 2

好的排序算法会尽量减少比较次数以实现良好的性能。这不是问题，而是这些排序算法的一个特性。如果将每个元素与其他元素进行比较，它不会改变结果。

如果顺序不符合您的预期，您应该仔细查看您的比较器。

Answer 3

它所做的比较是正确的，符合预期。如果 L > G 且 G > E 那么，根据比较规则，L > E.

比较器在这方面遵循正常的算术规则。 3 > 2 and 2 > 1 表示 3 > 1（传递性）。

你的问题可能是E是A的子树。正常情况下，它不应该在这种树中。拥有多个父代会使树处理变得相当复杂。如果您删除 link 并在进行比较时使用某种递归算法遍历树，它应该可以工作。

Answer 4

正如所指出的那样，您的比较器违反了比较器合同...但是按照您描述的方式进行自己的排序应该不会太复杂，您可能需要这样的东西：

import java.util.Collections;
import java.util.List;

public class NodeSorter {

    public void sort(List<Node> nodes) {
        Collections.sort(nodes, (x, y) -> Character.compare(x.getId(), y.getId()));
        for (int i = 0; i < nodes.size() - 1; i++) {
            for (int j = i + 1; j < nodes.size(); j++) {
                Node x = nodes.get(i);
                Node y = nodes.get(j);
                if (y.getChildren().contains(x)) {
                    nodes.remove(y);
                    nodes.add(i, y);
                    i--;
                    break;
                }
            }
        }
    }
}

此外，即使您想保留比较器用于某些东西，您也可以使用 Character.compare() 从中删除一半的逻辑，例如：

@Override
public int compare(Node o1, Node o2) {
    if (o1.getChildren().contains(o2)) {
        return -1;
    }

    if (o2.getChildren().contains(o1)) {
        return 1;
    }

    return Character.compare(o1.getId(), o2.getId());
}

Java 比较器不比较每个 object

Java Comparator doesn't compare each object

java

comparator