排序是Java中十分基础的功能。尽管平时经常用到，但都没关注具体怎么实现。本文以最常用的集合排序为切入点，分析下Java中集合排序、数组排序的用法，以及引用类型和基本类型排序的实现细节。梳理一遍才发现，底层排序算法比想象中要复杂的多。真应了《道德经》中说的，学之愈多，愈觉知之不足。

集合排序

Java中集合可以通过 java.util.Collections.sort 方法实现排序。

按sort方法形参不同，可将排序分为两类

基于Comparable

要求实现 java.lang.Comparable 接口

源码

Collections.sort()中只需要传入list

用法

String, Integer等类已经实现了Comparable接口，可以直接调用

Collections.sort(list);

自定义的类需要先实现Comparable接口，在compareTo方法中定义排序规则

public class DeviceWeight implements Comparable<DeviceWeight>{
    private String ip;
    private Integer weight;

    // 按weight升序排序
    @Override
    public int compareTo(DeviceWeight other) {
        return other.getWeight() - this.weight;
    }
}

基于Comparator

不要求实现java.lang.Comparable接口，但要提供一个java.util.Comparator的实现子类作为参数

源码

sort()需要传入list和Comparator实例

用法

要求按年龄排序

• 匿名内部类写法，实现 Comparator 接口，并重写compare方法

  Collections.sort(list, new Comparator<People>() {
      // 实现Comparator接口，重写compare方法，按年龄升序排序
      @Override
      public int compare(People o1, People o2) {
          return o1.getAge() - o2.getAge();
      }
  });

• lambda表达式写法

  Collections.sort(list, (o1, o2) -> o1.getAge() - o2.getAge());

• JDK1.8中写法

  list.sort(Comparator.comparingInt(People::getAge));

  其中 Comparator.comparingInt() 是1.8中的新方法

  

---

内部实现

在JDK1.8中，这两个 Collections.sort 方法底层都是调用的都是 java.util.List.sort 方法

List.sort 方法内部又调用了 java.util.Arrays.sort()方法

可以看到，集合的排序是通过泛型数组(T[])的排序实现的。

数组排序

java.util.Arrays 方法内包含多个sort方法，按范围可分为部分元素排序和全部元素排序，按数组类型又可以分为引用类型和基本类型（二者之间的排序逻辑不同）。

引用类型排序

引用类型又分为Object和泛型，分别对应是否指定Comparator<? super T> c的情况

Object数组

不指定Comparator实现子类则会进入此方法。

Arrays.sort(Object[] a)

此方法有两种排序，JDK1.8中默认LegacyMergeSort.userRequested = false，走ComparableTimSort.sort

如果要走老的归并排序，可以手动设置useLegacyMergeSort为true

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");

ComparableTimSort.sort

进入ComparableTimSort.sort。当数组长度<32，进行二分排序。当数组长度>=32，进行Tim排序（基于归并排序和插入排序的混合排序）

重点关注下countRunAndMakeAscending和binarySort 方法。二者都有调用了数组元素的compareTo方法，进行比较。如果对象未实现Comparable接口，那一定会报类型转换异常(java.lang.ClassCastException)

ComparableTimSort.countRunAndMakeAscending

ComparableTimSort.binarySort

泛型数组

指定Comparator会进入java.util.TimSort.sort方法

TimSort.sort

进入TimSort.sort，同样先判断数组长度，当数组长度<32，进行二分排序。当数组长度>=32，进行Tim排序（基于归并排序和插入排序的混合排序）

该方法同样调用了countRunAndMakeAscending和binarySort方法，二者都调用了c.compare用来比较

TimSort.countRunAndMakeAscending

TimSort.binarySort

引用类型排序总结

数组长度	所使用的排序算法
length < 32	二分排序
length >= 32	Tim排序

基础类型排序

Arrays中所有基础类型的排序，都会调用java.util.DualPivotQuicksort.sort()及其重载方法

以int[]为形参的sort方法为例，内部调用了以int[]为形参的DualPivotQuicksort.sort方法

Arrays.sort(int[] a)

DualPivotQuicksort.sort(int[], int, int, int[], int, int)

其内部排序规则如下：

当数组长度>=286，判断是否基本有序。基本有序则使用快排，基本无序则使用归并排序

当数组长度<286，进入快速排序

DualPivotQuicksort.sort(int[], int, int, boolean)

其中，如果数组长度<=47，直接使用插入排序

基础类型排序总结

数组长度	所使用的排序算法
length < 47	插入排序
47 <= length < 286	快速排序
length >= 286 且数组基本有序	归并排序
length >= 286 且数组基本无序	快速排序

参考资料

1. JDK中的排序：Arrays.sort的源码实现
2. Java 排序遇到的神坑，我替你踩了
3. MergeSort与TimSort，ComparableTimSort