java - 在快速排序中修改比较器

Question

整数数组的快速排序通过递归地划分整个数组的两半来工作——并在这样做时对数组进行排序。我知道分区需要 O(n)，并且因为它是在每一半(logN 次)上递归完成的，所以总成本为 O(NlogN)。

在 Cracking the Coding Interview 第 6 版中，问题 10.2 要求编写一个方法来对字符串数组进行排序，以便所有的变位词彼此相邻。作者提出了两种不同的解决方案——其中一种是对整个数组进行快速排序，结果是变位词最终会彼此相邻。

但是——她说这是时间 O(NlogN)。这就是我迷路的地方。对于整数数组，快速排序必须访问每个元素并根据一个元素是否大于另一个元素来交换整数。这是每 N 个元素的 O(1) 成本，总计为 O(N)。然而，作者建议的两个字符串的比较将两个字符串分解为一个 char 数组，对它们进行排序，然后进行比较。该过程将是每个字符串的 O(L logL)(其中 L 是字符串的长度).. 所以它是每 N 个字符串的 O(LlogL) 成本——这不是 O(NlogN(L LogL)) 吗？可能会迷失在数字中，但如果有人能向我解释作者的过程如何具有字符串比较的 O(NlogN) 复杂性，那将非常有帮助。以下是她的代码:

class AnagramComparator implements Comparator <String> {
  public String sortChars(String s) {
    char[] content = s.toCharArray();
    Arrays.sort(content)
    return new String(content);
  }
  public int compare(String s1, String s2) {
    return sortChars(s1).compareTo(sortChars(s2));
  }
}

Answer 1

作者可能假设字符串的最大长度是某个常数，因此字符串比较仍然是 O(1)。