Arrays.sort(sa, Comparator.comparing(i -> rank[i])); 这个 语句是怎么排序

这个语句使用了 Java 8 引入的 Lambda 表达式和 Comparator 接口，可以将后缀数组 `sa` 按照其对应的排名数组 `rank` 的大小进行排序。

具体来说，`Comparator.comparing(i -> rank[i])` 返回了一个比较器，该比较器会根据后缀数组 `sa` 中每个位置对应的排名数组 `rank` 的大小来进行比较。Lambda 表达式 `i -> rank[i]` 将后缀数组中的每个位置 `i` 映射到其对应的排名数组 `rank` 中的值。`Comparator.comparing` 方法则接受这个映射函数，并返回一个比较器，该比较器会按照映射函数的结果进行比较。

最后，`Arrays.sort` 方法接受后缀数组 `sa` 和比较器对象，并将 `sa` 按照比较器的规定进行排序。排序后，`sa` 中每个位置对应的后缀都按照字典序排列。

需要注意的是，这里使用的是稳定排序算法，因为在后缀数组中可能存在相同的后缀（例如字符串的前缀），这些后缀需要按照它们出现的顺序来进行排序，否则可能导致后面的 LCP 计算出现错误。稳定排序算法可以保证相同的元素在排序后仍然按照它们原来的顺序排列。