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

Question

我有一个项目清单：[foo, bar, baz, boo, abc, xyz]其中一些项目希望按特定顺序排序：foo after abcxyz 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 -> 0Comparing 'baz' to 'bar': no rule present -> 0Comparing 'boo' to 'baz': no rule present -> 0Comparing 'abc' to 'boo': no rule present -> 0Comparing 'xyz' to 'abc': no rule present -> 0Comparator 将运行，但它只会输出与您开始时相同的列表。似乎要使 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 => 1

• abc => 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> rules = List.of("abc", "foo", "xyz", "baz");
Comparator<String> comparator = Comparator.comparing((String s) -> rules.indexOf(s));

然后你就可以参加比赛了。这个比较器使用键提取函数按索引对项目进行排序——基本上是一个将值转换为另一个值的函数，然后按该值排序。由于 list.indexOf() 为规则中未提及的项目返回 -1，而为规则中提及的项目返回零或更高，因此未提及的项目将始终排在前面，然后按规则顺序在规则中提及的项目之后。

（如果您希望规则中未提及的项目放在最后，那么您的密钥提取器函数需要使用 contains，并为不在列表中的项目返回 Integer.MAX_VALUE。）

由于 Java 的排序算法 TimSort 是一种稳定的排序算法，所有索引为 -1 的值将按照它们在列表排序之前的相同顺序返回。

更新：如何将规则“编译”成列表

这可以通过利用稳定排序算法来完成。将规则中提到的每个项目添加到列表中，然后按每个单独的规则对该列表进行一次单独排序。例如：规则“foo after abc”将是一个键提取器函数，它为 abc 返回 0，为 foo 返回 1，为其他所有返回 Integer.MAX_VALUE。

为每个规则对列表进行一次排序后，您需要在一次通过中再次检查每个规则，以确保所有规则仍然成立。（如果没有，你就有一个不可能的规则集。）