当只知道一些关系时，如何在 Java 中对非数字对象进行排序？

Question

我有一个项目清单：

[foo, bar, baz, boo, abc, xyz]

其中一些项目希望按特定顺序排序：

foo after abc

xyz before baz

只要遵守所有给定的规则，其他项目的顺序无关紧要。

以下是一些可能的排序顺序：

[abc, foo, xyz, baz, bar, boo]

[abc, xyz, foo, baz, bar, boo]

[abc, foo, bar, boo, xyz, baz]

[xyz, baz, bar, boo, abc, foo]

使用 aComparator似乎不起作用，因为设计一个列表可能会导致它失败。例如，如果我们的 compare 方法如下所示：

list.sort((a, b) -> {

    if (a.isAfter(b)) {

        return 1;

    } else if (a.isBefore(b)) {

        return -1;

    }

    return 0;

});

我们针对 运行它[foo, bar, baz, boo, abc, xyz]，该方法将执行如下操作：

Comparing 'bar' to 'foo': no rule present -> 0

Comparing 'baz' to 'bar': no rule present -> 0

Comparing 'boo' to 'baz': no rule present -> 0

Comparing 'abc' to 'boo': no rule present -> 0

Comparing 'xyz' to 'abc': no rule present -> 0

Comparator 将运行，但它只会输出与您开始时相同的列表。似乎要使 Comparator 正常工作，您需要知道列表中任意两个项目之间的关系，而不仅仅是其中一些项目。

知道这一点，一种解决方案是将所有具有规则的元素移动到一个单独的列表中，对该列表进行排序，然后将其与其余元素合并。通过这种方式，我们确实知道我们正在比较的所有项目之间的关系。但是，要使其正常工作，您必须为每个规则创建单独的列表。否则，您可能会再次遇到完全相同的问题：

[foo, bar, baz, boo, abc, xyz] // original

[foo, baz, abc, xyz] // elements with rules

[foo, baz, abc, xyz] // elements with rules **after comparator**

[foo, baz, abc, xyz, bar, boo] // merged with the rest, rules not satisfied

为每个可能出现的规则创建列表并不是很优雅。我可以使用另一种分拣机来适应我正在寻找的行为吗？

Answer 1

此类问题有多种解决方案。一种解决方案是手动进行排序：您遍历数组，当您看到 a 时foo，您在剩余的数组中搜索所有内容abc并将它们放在后面（或以相反的顺序：当您看到 a 时abc，您搜索所有foo在已经传递的数组中并将它们放在前面）。另一种解决方案是进行多种排序（每个规则一个，在本例中为 2），并且每次创建一个包含对 [value, number] 的数组，其中数字取决于原始数组中的值。对于第一条规则，我们可以有：foo => 1abc => 0所有其他值 => 最后使用的值，或 0。所以数组[foo, bar, baz, boo, abc, xyz]将被翻译成 [(foo,1), (bar,1), (baz,1), (boo,1), (abc,0), (xyz,0)]. 当我们的排序是用在对的数字，我们可以得到下面的数组： [(abc,0), (xyz,0), (foo,1), (bar,1), (baz,1), (boo,1)]。这是排序的。现在，如果我们应用第二规则（xyz=> 0，baz=> 1），我们得到以下的数组： [(abc,0), (xyz,0), (foo,0), (bar,0), (baz,1), (boo,1)]。你现在有一个排序的数组。您可以通过使用 [number of rules]+1 个元素的元组来改进这一点，并在第一次分配所有值，并对sort每个规则应用一次该函数，每次都选择要排序的元组元素。根据规则的数量和数组的大小，第一种方法可能比第二种方法更好。如果你有很多规则和一个小数组，我想我会更喜欢第一种方法。相反，如果你有一些规则和一个大数组，我会建议第二种方法。这个选择的原因很简单：如果你有大数组，第二种方法将依赖于sort语言中集成的函数，速度更快。相反，如果您有很多规则，则第二种方法将意味着多次调用排序函数，无论规则数量如何，第一种方法都会花费大约相同的时间

Answer 2

最好的办法是将所有规则“编译”到一个列表中。例如，上面提到的两个规则会生成这个列表：[“abc”，“foo”，“xyz”，“baz”]（或 ["xyz", "baz", "abc", "foo"]。你会得到不同的答案，但仍会遵循规则）。除非有一个规则循环，否则您将始终能够做到这一点，在这种情况下，它们无法遵循。（“abc 在 def 之前，def 在 ghi 之前，ghi 在 abc 之前”是一个不可能的规则集的例子）。但如果它们不是不可能的，那么您可以将它们编译成一个列表——基本上所有命名的术语都按排名顺序排列。您的比较器只是该列表中的位置，如果该项目不在列表中，则为负数。借助 Java 8/9 的优势，您可以轻松地编写该比较器，如下所示：List<String>&nbsp;rules&nbsp;=&nbsp;List.of("abc",&nbsp;"foo",&nbsp;"xyz",&nbsp;"baz"); Comparator<String>&nbsp;comparator&nbsp;=&nbsp;Comparator.comparing((String&nbsp;s)&nbsp;->&nbsp;rules.indexOf(s));然后你就可以参加比赛了。这个比较器使用键提取函数按索引对项目进行排序——基本上是一个将值转换为另一个值的函数，然后按该值排序。由于 list.indexOf() 为规则中未提及的项目返回 -1，而为规则中提及的项目返回零或更高，因此未提及的项目将始终排在前面，然后按规则顺序在规则中提及的项目之后。（如果您希望规则中未提及的项目放在最后，那么您的密钥提取器函数需要使用 contains，并为不在列表中的项目返回 Integer.MAX_VALUE。）由于 Java 的排序算法 TimSort 是一种稳定的排序算法，所有索引为 -1 的值将按照它们在列表排序之前的相同顺序返回。更新：如何将规则“编译”成列表这可以通过利用稳定排序算法来完成。将规则中提到的每个项目添加到列表中，然后按每个单独的规则对该列表进行一次单独排序。例如：规则“foo after abc”将是一个键提取器函数，它为 abc 返回 0，为 foo 返回 1，为其他所有返回 Integer.MAX_VALUE。为每个规则对列表进行一次排序后，您需要在一次通过中再次检查每个规则，以确保所有规则仍然成立。（如果没有，你就有一个不可能的规则集。）