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

2020/02/07 Java

此文首发于我的Jekyll博客:zhang0peter的个人博客


之前写了一篇博客: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的内置排序算法也是TimSortsorting - What algorithm does python’s sorted() use? - Stack Overflow