使用Array.sort对字符串数组中的变位词分组排序问题排查

嘿，我太懂你这种卡壳的感觉了——想把变位词归为一组排序，明明思路没问题，但Comparator里的问题就是揪不出来，结果完全不符合预期对吧？别慌，咱们先聊聊Comparator实现时最容易踩的几个坑，再给你一套靠谱的解决方案。

咱们先排查你可能踩的雷：

• 错误1：用哈希值代替唯一标识比较
  很多人图省事，直接用return s1.hashCode() - s2.hashCode()来比较，但哈希值是可能碰撞的——不同的字符串可能有相同哈希，相同变位词也可能因为某些情况哈希不同（虽然概率低，但绝对不可靠），这会导致变位词分组混乱。
• 错误2：忽略大小写或特殊字符处理
  比如"Listen"和"silent"，如果不统一转成小写/大写再生成标识，排序后的字符序列会不一样，自然不会被归为一组。要是字符串里有特殊字符，也得考虑是否需要统一处理。
• 错误3：Comparator违反排序契约
  排序要求Comparator满足自反性、对称性、传递性：比如a.compare(b) == -b.compare(a)，且如果a.compare(b)=0、b.compare(c)=0，那么a.compare(c)必须也等于0。很多人会写return key1.equals(key2) ? 0 : 1，这就破坏了传递性，排序算法会直接乱掉。

核心逻辑是：给每个变位词生成一个唯一的标识（比如排序后的字符序列），Comparator先比较这个标识，相同标识的就是一组，组内顺序你可以自由决定（比如按原字符串排序，或者保留原顺序）。

Java示例代码 #

import java.util.Arrays;
import java.util.Comparator;

public class AnagramGroupComparator implements Comparator<String> {
    @Override
    public int compare(String str1, String str2) {
        // 生成变位词的唯一标识：统一转小写后排序字符（忽略大小写的话加这步，不需要就去掉toLowerCase）
        char[] chars1 = str1.toLowerCase().toCharArray();
        char[] chars2 = str2.toLowerCase().toCharArray();
        Arrays.sort(chars1);
        Arrays.sort(chars2);
        
        String groupKey1 = new String(chars1);
        String groupKey2 = new String(chars2);
        
        // 先按组key排序，确保变位词归为一组
        int groupCompare = groupKey1.compareTo(groupKey2);
        if (groupCompare != 0) {
            return groupCompare;
        }
        
        // 组内可以按原字符串排序（不需要的话直接返回0，组内顺序由排序算法决定）
        return str1.compareTo(str2);
    }
}

使用方式 #

public static void main(String[] args) {
    String[] wordArray = {"eat", "Tea", "tan", "ate", "Nat", "bat"};
    Arrays.sort(wordArray, new AnagramGroupComparator());
    
    // 输出结果：[ate, eat, Tea, bat, Nat, tan]（组内按原字符串排序，且忽略大小写分组）
    for (String word : wordArray) {
        System.out.print(word + " ");
    }
}

简化版（Java 8+ Lambda） #

如果不想写单独的类，用Lambda可以更简洁：

Arrays.sort(wordArray, (s1, s2) -> {
    char[] c1 = s1.toLowerCase().toCharArray();
    char[] c2 = s2.toLowerCase().toCharArray();
    Arrays.sort(c1);
    Arrays.sort(c2);
    return new String(c1).compareTo(new String(c2));
});

如果你其实更关注分组而非严格排序，用Map<String, List<String>>会更直观：把排序后的字符串作为key，遍历数组把每个字符串加入对应的列表，最后把所有列表合并就是分组后的结果。不过既然你要的是排序，上面的Comparator方案完全能满足需求。

内容的提问来源于stack exchange，提问作者J.dawg