java - 某些字符串使用基本字符比较的 sortWith 失败

Question

我想按如下方式应用自定义排序比较器:

 myString.sortWith{ case (c1,c2) => c1.compareTo(c2) <= 0}

这应该按照代码点值对字符串的字符进行排序。

然而它并不总是有效。考虑一个简单的字符串 cab312:

val str = "cab312"

str.sortWith{ case (c1,c2) => c1.compareTo(c2) <= 0}
res0: String = 123abc

这很好用。考虑一个更复杂的字符串:

scala> val str = "TOADS POOLS hoppin good service & repair"
str: String = TOADS POOLS hoppin good service & repair

scala> str.sortWith{ case (c1,c2) => c1.compareTo(c2) <= 0}
java.lang.IllegalArgumentException: Comparison method violates its general contract!
  at java.util.TimSort.mergeHi(TimSort.java:899)
  at java.util.TimSort.mergeAt(TimSort.java:516)
  at java.util.TimSort.mergeCollapse(TimSort.java:441)
  at java.util.TimSort.sort(TimSort.java:245)
  at java.util.Arrays.sort(Arrays.java:1438)
  at scala.collection.SeqLike$class.sorted(SeqLike.scala:648)
  at scala.collection.immutable.StringOps.sorted(StringOps.scala:29)
  at scala.collection.SeqLike$class.sortWith(SeqLike.scala:601)
  at scala.collection.immutable.StringOps.sortWith(StringOps.scala:29)
  ... 32 elided

所以 .. 我们得到一个 java.lang.IllegalArgumentException: Comparison method violates its general contract!

这是怎么回事？同一个 comparator 怎么会既成功又失败。这是 timsort 中的错误吗？无论如何有解决方法吗？

Answer 1

文档明确指出sortWith需要一个函数 lt返回 true当且仅当第一个操作数先于(严格Less Than)第二个操作数:

lt the comparison function which tests whether its first argument precedes its second argument in the desired ordering.

你的 c1.compareTo(c2) <= 0对于相等的元素返回 true，因此违反了 lt 的约定.改变 <=至 <消除了问题:

str.sortWith{ case (c1,c2) => c1.compareTo(c2) < 0}
//"      &ADLOOOPSSTacdeeeghiiinoooppprrrsv"