浮云的博客

Java数组排序： Array-ArrayList-List-Collections.sort()/List.sort()/Arrays.sort()

2020/02/07 Java 共 2179 字，约 7 分钟

之前写了一篇博客：Java：获取数组中的子数组的多种方法

现在在做LeetCode题目时想要对数组进行排序，于是想到Java中是否存在C++的标准库中的std::sort()。

Java的排序分为2种，一种是ArrayList或者List；另一种则是Array

ArrayList/List 的排序：Collections.sort()/List.sort()

先说一下排序的各种方法的具体使用示例：sort List

代码如下：

        List<String> strings = Arrays.asList("zoo", "foo", "bar", "baz");
        Collections.sort(strings); 
        System.out.println(strings.toString());

        List<String> strings = Arrays.asList("zoo", "foo", "bar", "baz");
        strings.sort(null);
        System.out.println(strings.toString());

Collections.sort()函数本质上是调用List.sort():

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

对于所有实现了接口List的类，如ArrayList，自然继承了函数sort，而List.sort()本质上调用了Arrays.sort()。

    //List.sort()
    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);
        }
    }

而Arrays.sort()函数的具体实现如下：

    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);
        }
    }
    public static void sort(Object[] a) {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a); //旧的排序算法，不推荐
        else
            ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
    }
    private static void legacyMergeSort(Object[] a) {
        Object[] aux = a.clone();
        mergeSort(aux, a, 0, a.length, 0);
    }

至于TimSort这种排序算法的具体实现，参考这篇博客:Java内置排序算法：Timsort详解

如果想自定义Comparator，参考这篇博客：Java 8 Comparator: How to Sort a List - DZone Java

Array 的排序：Arrays.sort()

List中存放的只能是类的对象，或者包装类的对象，如：Long, Integer。

而如果我们把对象直接存放在数组中，也就是 Array 中，如 存放int, long在 Array 数组中，排序的方法如下：

        int[] nums = {-2, 5, -1};
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));

可以看出不管是基本类型数组，还是List，最终都是调用Arrays.sort进行最终的排序。

因为函数的对象是基本类型，因此Arrays.sort会直接调用函数进行排序，使用的排序算法是Dual-Pivot Quicksort:

    public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

使用的不是普通的快排，而是双指针快排，最坏的时间复杂度为O(n log(n))

看到这里会产生疑问，为什么对List的排序使用算法TimSort，而对数组的排序使用算法Dual-Pivot Quicksort

网上有个讨论：algorithm - Comparison between timsort and quicksort - Stack Overflow

快排适合原始数组是因为内存的局部性和缓存。

里面有个推测说，对象数组存放的仅仅是对象的引用，而实际的比较需要从堆中读取对象，因此TimSort更合适。

Python中的所有数据都是对象，因此Python的内置排序算法也是TimSort：sorting - What algorithm does python’s sorted() use? - Stack Overflow

文档信息

Table of Contents