彻底理解 Java 中的自然排序和字典排序

概述

在不少涉及到排序的 Api 中，都会提到自然排序或者字段排序，那么怎么定义自然排序和字典排序呢？特别是涉及到中文的时候，自然排序到底按什么排序呢？本文将会和大家一起一探究竟。

那些涉及到自然排序的地方

1、java.util.Collections.sort

public static <T extends Comparable<? super T>> void sort(List<T> list);

文档中是这么描述的 sort 方法的：

Sorts the specified list into ascending order, according to the natural ordering of its elements.All elements in the list must implement the Comparable interface ...

natural ordering 翻译成中文便是自然排序。

注意：下文中 Collections.sort 如无特殊说明，都是特指该签名的方法，因为 Collections 还包含一个不同签名的 sort 方法。

2、TreeMap

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

在构造 TreeMap 的时候，如果不指定 Comparator，TreeMap 会对 key 进行自然排序。使用自然的排序的例子还有很多，我们就到此为止了。

尝试理解自然排序

提到自然排序，我们第一反应就是阿拉伯数字从小到大排序，然后就是英文字母按照 abcde ... 的顺序排序。好像自然排序是很容易理解的一个概念。但是仔细一想就不是那么回事了！

前面提到的 Collections.sort 方法是一个泛型方法，自然可以接收任何类型的 list。让我们来排序中文看看是什么结果。

@Test
public void testNaturalOrder() {
    List<String> list = new ArrayList<>(Arrays.asList("自", "然", "排", "序"));
    Collections.sort(list);
    // 输出结果：[序, 排, 然, 自]
    System.out.println(list);
}

这个地方自然排序到底按照什么排序呢？按照拼音顺序吗？从上面的输出结果可以很容易看出答案是否定的。从输出结果来看完全没规律。在解开谜底之前，让我们先来尝试排序一个自定义的对象。

// 省略 getter 和 setter
public static class User {
  private String name;
  private User(String name) {
      this.name = name;
  }
}
@Test
public void testNaturalOrder2() {
  List<User> list = new ArrayList<>(Arrays.asList(new User("lucy"), new User("lili")));
  Collections.sort(list);
  System.out.println(list);
}

这段代码，编译就会报错，因为 Collections.sort 要求 List 中元素的类型必须实现 Comparable 接口。问题到这里基本上清楚了，所谓的自然排序就是要求参与排序的元素所属类必须实现 Comparable 接口。由 Comparable 接口中的 compareTo 方法来决定排序的规则。

public int compareTo(T o);

好巧不巧，Integer 中的 compareTo 方法正是按照数字大小从小到大排序的，这和我们从小理解的自然排序是一致的。

更巧合的是纯英文字符串恰好就是按照字典顺序排序的，然而对于中文就不灵了。那么问题来了中文的自然排序到底是怎么排序的呢？

要搞清楚这个问题，只需要看看 String 中的 compareTo 方法究竟是怎么排序不就可以了吗？以下代码来自 java8，虽然从 Java9 开始正式引入了 Compact Strings，但是不影响问题的理解。

public int compareTo(String anotherString) {
    int len1 = value.length;
    int len2 = anotherString.value.length;
    int lim = Math.min(len1, len2);
    char v1[] = value;
    char v2[] = anotherString.value;

    int k = 0;
    while (k < lim) {
        char c1 = v1[k];
        char c2 = v2[k];
        if (c1 != c2) {
            return c1 - c2;
        }
        k++;
    }
    return len1 - len2;
}

不论是中文还是英文，字符串的比较，实际比较的是字符串内部的 char 数组，而 char 是采用 utf-16 编码的。现在让我们再来理解下 testNaturalOrder 为什么输出 [序, 排, 然, 自]。

从 https://www.compart.com/en/unicode 可以查到“自然排序”这几个字的 utf-16 编码的值分别为 0x81EA、0x7136、0x6392 和 0x5E8F。比较这几个编码值的大小就可以得出输出结果为 [序, 排, 然, 自]。

从这里可以看出，中文的自然排序和拼音没有任何关系，中文的自然排序也没什么实际意义。如果要想中文按照拼音排序，可以使用 Collections 中另一个 sort 方法，该方法允许指定一个 Comparator。通过 Comparator 可以自定义任何排序规则。

总结

Java 实现中自然排序并非我们从小理解的自然排序，自然排序是由排序对象所属类实现的 compareTo 方法决定的。