Arrays.sort 和 Collections.sort 实现原理和区别


Collection和Collections区别

java.util.Collection 是一个集合接口 。它提供了对集合对象进行基本操作的通用接口方法。

java.util.Collections 是针对集合类的一个帮助类 ,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全等操作。 然后还有混排(shuffle)、反转(reverse)、替换所有的元素(fill)、拷贝(copy)、返回Collection中最小元素(min)、返回Collection中最大元素(max)、返回指定源列表中最后一次出现指定目标列表的起始位置( lastIndexOfSubList )、返回指定源列表中第一次出现指定目标列表的起始位置( IndexOfSubList )、根据指定的距离循环移动指定列表中的元素(rotate);

事实上Collections.sort方法底层就是调用的Arrays.sort方法

Collections 中的sort() 方法如下:

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

其中调用的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);
    }

legacyMergeSort (a,c):归并排序

TimSort.sort() : Timsort 排序,结合了合并排序(merge sort)和插入排序(insertion sort)而得出的排序算法


Timsort的核心过程 :

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

综上述过程,Timsort算法的过程包括 :

1、如何数组长度小于某个值,直接用二分插入排序算法

2、找到各个run,并入栈

3、按规则合并run


原文链接:https://www.cnblogs.com/firecode7/p/13275895.html