9、Arrays.sort 实现原理和 Collection 实现原理(9、Arrays. Sort implementation principle and collection implementation principle)

  • java.util.Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法
  • java.util.Collections 是针对集合类的一个帮助类。它提供一系列静态方法实现对各种集合的搜索、排序、线程安全等操作。 然后还有混排(shuffle)、反转(reverse)、替换所有的元素(fill)、拷贝(copy)、返回Collection中最小元素(min)、返回Collection中最大元素(max)、返回指定源列表中最后一次出现指定目标列表的起始位置( lastIndexOfSubList )、返回指定源列表中第一次出现指定目标列表的起始位置( IndexOfSubList )、根据指定的距离循环移动指定列表中的元素(rotate)
  • 事实上Collections.sort方法底层就是调用的Arrays.sort方法
@Test
    public void test_09() {
        /**
         * 9、Arrays.sort 实现原理和 Collection 实现原理
         */
        Integer[] test09 = new Integer[]{1223, 321, 432};
        Arrays.sort(test09);
        log.info(JSON.toJSONString(test09));
        List<Integer> test09_list = new ArrayList<Integer>();
        test09_list.add(1323);
        test09_list.add(321);
        test09_list.add(432);
        Collections.sort(test09_list);
        log.info(JSON.toJSONString(test09_list));
    }

2022-01-15 13:08:31.887  INFO 2228 --- [           main] com.kolaer.cms.CmsApplicationTests       : [321,432,1223]
2022-01-15 13:08:31.888  INFO 2228 --- [           main] com.kolaer.cms.CmsApplicationTests       : [321,432,1323]
// 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);
        }
    }

//legacyMergeSort (a,c):归并排序
//TimSort.sort() : Timsort 排序,结合了合并排序(merge sort)和插入排序(insertion sort)而得出的排序算法
public static void sort(Object[] a) {
  if (LegacyMergeSort.userRequested)
      legacyMergeSort(a);
  else
      ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

 /**
         * Timsort的核心过程:
         *   TimSort 算法为了减少对升序部分的回溯和对降序部分的性能倒退,将输入按其升序和降序特点进行了分区。排序的  输入的单位不是一个个单独的数字,而是一个个的块-分区。其中每一个分区叫一个run。针对这些 run 序列,每次拿一个 run 出来按规则进行合并。每次合并会将两个 run合并成一个 run。合并的结果保存到栈中。合并直到消耗掉所有的 run,这时将栈上剩余的 run合并到只剩一个 run 为止。这时这个仅剩的run 便是排好序的结果。
         *
         * 综上述过程,Timsort算法的过程包括 :
         *   1、如何数组长度小于某个值,直接用二分插入排序算法 
         *   2、找到各个run,并入栈 
         *   3、按规则合并run 
         */
————————
  • java. util. Collection is a collection interface. It provides a general interface method for basic operations on collection objects
  • java. util. Collections is a help class for collection classes. It provides a series of static methods to realize the search, sorting, thread safety and other operations of various collections. Then there are shuffle, reverse, fill, copy, min, Max, and lastindexofsublist Returns the starting position (indexofsublist) where the specified target list first appears in the specified source list, and circulates the elements in the specified list according to the specified distance (rotate)
  • 事实上Collections.sort方法底层就是调用的Arrays.sort方法
@Test
    public void test_09() {
        /**
         * 9、Arrays.sort 实现原理和 Collection 实现原理
         */
        Integer[] test09 = new Integer[]{1223, 321, 432};
        Arrays.sort(test09);
        log.info(JSON.toJSONString(test09));
        List<Integer> test09_list = new ArrayList<Integer>();
        test09_list.add(1323);
        test09_list.add(321);
        test09_list.add(432);
        Collections.sort(test09_list);
        log.info(JSON.toJSONString(test09_list));
    }

2022-01-15 13:08:31.887  INFO 2228 --- [           main] com.kolaer.cms.CmsApplicationTests       : [321,432,1223]
2022-01-15 13:08:31.888  INFO 2228 --- [           main] com.kolaer.cms.CmsApplicationTests       : [321,432,1323]
// 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);
        }
    }

//legacyMergeSort (a,c):归并排序
//TimSort.sort() : Timsort 排序,结合了合并排序(merge sort)和插入排序(insertion sort)而得出的排序算法
public static void sort(Object[] a) {
  if (LegacyMergeSort.userRequested)
      legacyMergeSort(a);
  else
      ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

 /**
         * Timsort的核心过程:
         *   TimSort 算法为了减少对升序部分的回溯和对降序部分的性能倒退,将输入按其升序和降序特点进行了分区。排序的  输入的单位不是一个个单独的数字,而是一个个的块-分区。其中每一个分区叫一个run。针对这些 run 序列,每次拿一个 run 出来按规则进行合并。每次合并会将两个 run合并成一个 run。合并的结果保存到栈中。合并直到消耗掉所有的 run,这时将栈上剩余的 run合并到只剩一个 run 为止。这时这个仅剩的run 便是排好序的结果。
         *
         * 综上述过程,Timsort算法的过程包括 :
         *   1、如何数组长度小于某个值,直接用二分插入排序算法 
         *   2、找到各个run,并入栈 
         *   3、按规则合并run 
         */