首页 文章

Java Comparator不会比较每个对象

提问于
浏览 次
2

我在使用Java Comparator 时遇到了一些问题 . 所以我有一个父节点，它有一个子列表 . 我想对这些孩子进行排序，看起来很简单，但是当 Comparator 进行排序时它只会检查特定对象的某些对象，然后我想它会推断出对象的位置，比如 a 是否在 d 之前， f 在 d 之后， b 在 d 之前，这意味着 b 在 f 之前 .

以下是我当前设置的示例 . 我有一个父节点 a 有4个子节点 b ， e ， l ， g . 当我对这些孩子进行排序时，我希望订单是 b ， g ， l ， e ，因此按字母排序并始终确保父节点排在第一位 .

（借口粗制滥造）

很简单，我有一个 Node 类，它包含一个ID，所以它的字母然后是一个子列表 .

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 类，首先检查节点是否是你的孩子，然后如果他们你先去，反之亦然，然后按字母顺序排序 .

@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，所以它无法知道应该先行 .

java comparator

4 回答

  • 1

    它所做的比较是正确的，也是预期的 . 如果L> G且G> E则根据比较器的规则，L> E.

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

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

    回复于
  • 1

    您的订购违反了 Comparator 的 Contract ：

    实现者还必须确保关系是可传递的：（（compare（x，y）> 0）&&（compare（y，z）> 0））表示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 ，因此可能会产生异常或意外结果 .

    回复于
  • 4

    良好的排序算法试图最小化比较的数量，以实现良好的性能 . 这不是问题，而是这些排序算法的一个特征 . 如果将每个元素与每个其他元素进行比较，则不会更改结果 .

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

    回复于
  • 0

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

    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());
}
    回复于

相关问题