java - Collections.sort() 不适用于所有成员

Question

我正在尝试使用 Collections.sort() 对列表进行排序，并注意到所有成员都已排序:

这是我的输入，.compareTo() 内部的打印，以及输出:

5 4 3 2 1     // Original
me = 4: o = 5 // A printout at each entry into .compareTo()
me = 3: o = 4
me = 3: o = 5
me = 2: o = 5
me = 2: o = 3
me = 1: o = 3
me = 1: o = 2
4 5 3 2 1     // Final output (1 should be at the beginning though)

我的排序规则是:

1<4
3<2
4<5

我的实现是:

        List<Task> tasks = new TaskList();
        Task.create(tasks); // creates a list 5 4 3 2 1 
        while (scan.hasNext()) {
            String line = scan.next();
            Task.rules.add(line); // address the rules such as "1<4"
        }
        System.out.println(tasks);
        Collections.sort(tasks);

以及compareTo()实现:

    @Override
    public int compareTo(Object arg0) {
        int me = id;
        int o = ((Task) arg0).id;
        System.out.println("me = " + me + ": o = " + o);
        for (String s : rules) { // rules is an array of strings "1<4" etc
            int left = Integer.valueOf(s.substring(0, 1));
            int right = Integer.valueOf(s.substring(2));
            char op = s.charAt(1);

            boolean meLeft = left == me;
            boolean oLeft = left == o;
            boolean meRight = right == me;
            boolean oRight = right == o;

            if (meLeft && oRight) {
                if (op == '<') { // me < other
                    return -1;
                } else
                    return 1;
            } else if (oLeft && meRight) {
                if (op == '<') {// other < me
                    return 1;
                } else {
                    return -1;
                }
            }
        }
        return 0;
    }

正如您从顶部的“me = M, o = O”中看到的，Collections.sort() 并未迭代列表中的所有成员!

我希望以下内容能够显示每个成员“我”与所有其他成员“o”的比较，所以我预计这个问题顶部的列表会更长!我相信它的大小应该是 N^2...

Answer 1

您的compareTo方法以两种方式破坏了该方法的契约。

1) 传递性表示如果 x.compareTo(y) > 0和y.compareTo(z) > 0然后x.compareTo(z) > 0 。你的方法打破了这个，因为 5 > 4和4 > 1 ，但是5>1不是你的规则之一。

2) compareTo还必须满足条件:如果 x.compareTo(y) == 0然后sgn(x.compareTo(z)) == sgn(y.compareTo(z))对于所有人z 。你的方法打破了这个，因为 5.compareTo(1) == 0 ，而5.compareTo(4)和1.compareTo(4)具有相反的符号。

如果您不符合 compareTo 的契约(Contract)，sort的结果是不可预测的。但就您的情况而言，我们可以看到发生了什么。 4, 5, 3, 2, 1 按顺序排列，因为 4 < 5 = 3 < 2 = 1 。 (我使用 = 表示 compareTo 方法返回 0)。没有>在该链中签名，因此没有理由继续排序。

如果你想让1排在前面，除了让你的compareTo方法满足上述两个条件，您将必须添加至少一条涉及 [1, 4, 5] 中的内容和 [2, 3] 中的内容的规则。只要没有这样的规则，末尾的 1 就没有理由超越 2 和 3。