我有一個項目清單：[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為每個可能出現的規則創建列表并不是很優雅。我可以使用另一種分揀機來適應我正在尋找的行為嗎？
2 回答
慕桂英3389331
TA貢獻2036條經驗 獲得超8個贊
此類問題有多種解決方案。
一種解決方案是手動進行排序：您遍歷數組，當您看到 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語言中集成的函數，速度更快。相反，如果您有很多規則，則第二種方法將意味著多次調用排序函數，無論規則數量如何，第一種方法都會花費大約相同的時間
尚方寶劍之說
TA貢獻1788條經驗 獲得超4個贊
最好的辦法是將所有規則“編譯”到一個列表中。例如，上面提到的兩個規則會生成這個列表：
[“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。
為每個規則對列表進行一次排序后，您需要在一次通過中再次檢查每個規則，以確保所有規則仍然成立。（如果沒有，你就有一個不可能的規則集。）
添加回答
舉報
0/150
提交
取消