java - 按对象的边界将集合排序到链中

Question

比方说，我们有一场接力赛。团队的每个成员都走自己的路，将棍子传递给团队的下一个成员。我有课，描述了轨道号(每个团队都有自己的轨道号)和两个名字。第一个名字是轨道 N 部分的棍子所有者，第二个名字是轨道的下一部分 (N+1) 的棍子所有者。

class StickTransfer {
    int trackId;
    String stickFrom;
    String stickTo;
}

我的任务是按照 1) 跟踪 2) 按棍子移动的顺序对 StickTransfer 的所有对象进行排序。

例如假设有一个团队在轨道 1 上，Alex -> John -> Smith -> Adam。

list.add(new StickTransfer(1, "John", "Smith");
list.add(new StickTransfer(1, "Alex", "John");
list.add(new StickTransfer(1, "Smith", "Adam");

order(list)
// After that I want to get:
// Alex - John - first entry
// John - Smith - second entry
// Smith - Adam - third entry

所以，一开始我决定使用 Java 的这种比较器进行排序:

Comparator.comparing(StickTransfer::getTrackId)
            .thenComparing((o1, o2) -> {
                if (o1.getStickFrom().equals(o2.getStickTo())) {
                    return 1;
                }
                if (o1.getStickTo().equals(o2.getStickFrom())) {
                    return -1;
                }
                return 0;
            });

但我遇到了一个问题，使用这个比较器，一些条目仍然未排序。我认为那是因为它并不是一个很好的比较器。

现在我有一些问题:

1) 是否可以为标准 java 排序方法编写正确的比较器？

2)如果没有，有没有办法用一些Java标准方法来解决这个问题？

3)这样的算法问题有名字吗？

---

错误排序的例子:右顺序:X -> Y -> A -> B -> C -> D -> E

    StickTransfer stickTransferArr[] = {
            new StickTransfer(1, "A", "B"),
            new StickTransfer(1, "C", "D"),
            new StickTransfer(1, "B", "C"),
            new StickTransfer(1, "X", "Y"),
            new StickTransfer(1, "Y", "A"),
            new StickTransfer(1, "D", "E")
    };

    Arrays.sort(stickTransferArr, cmp);

结果:

[{track=1, [A - > B]}, {track=1, [B - > C]}, {track=1, [C - > D]}, {track=1, [X - > Y]}, {track=1, [Y - > A]}, {track=1, [D - > E]}]

Answer 1

3) Is there a name for such algorithmic problem?

您遇到的问题称为topological sorting .

1) Is it possible to write a right comparator for standard java sort method?

没有。如果你有两个以上的元素，就会有不能直接比较的元素。在您的示例中:StickTransfer(1, "Alex", "John") 和 StickTransfer(1, "Smith", "Adam") - 其中一个在前面？不看其他元素是不可能知道的。

2) If not, is there a way to resolve this problem with some of Java standard methods?

是的，有很多实现，例如: Sample Directed Graph and Topological Sort Code

从根本上说，您可以在图上使用深度优先搜索对其进行拓扑排序。