Arrays.sort和Collections.sort实现原理

发表于 | 分类于 |

事实上，在使用Collections.sort(list)的时候，就调用list.sort()

1
2
3
public static <T extends Comparable<? super T>> void sort(List<T> list) {
        list.sort(null);
}

我们在深入进去后，发现其实调用的就是Array.sort()

1
2
3
4
5
6
7
8
9
10
@SuppressWarnings({"unchecked", "rawtypes"})
    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

而在Array.sort中，会根据该对象是否能够通过归并排序来选择不同的排序方式。

1
2
3
4
5
6
7
8
9
10
public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {
            sort(a);
        } else {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }

  • legacyMergeSort：归并排序
  • TimSort
    ：结合归并排序和插入排序的一种排序算法

TimSort 算法为了减少对升序部分的回溯和对降序部分的性能倒退，将输入按其升序和降序特点进行了分区。排序的输入的单位不是一个个单独的数字，而是一个个的块-分区。其中每一个分区叫一个run。针对这些 run 序列，每次拿一个 run 出来按规则进行合并。每次合并会将两个 run合并成一个 run。合并的结果保存到栈中。合并直到消耗掉所有的 run，这时将栈上剩余的 run合并到只剩一个 run 为止。这时这个仅剩的 run 便是排好序的结果。