Collections.sort()方法解析

2019-11-06 06:02:04

字体：大中小

来源：转载

供稿：网友

首先注意这里调用sort方法的是Collections类，他是集合框架中的一员,其中实现了大量的工具方法，有时间可以自行查看：这里写图片描述

下面是一个简单的测试类：

import java.util.*;/** * Created by Admin on 2017/3/7. */public class CollectionTest { public static void main(String[] args){ List<Integer> list_1 = new ArrayList<Integer>(Arrays.asList(2,1,4,8,5)); System.out.PRintln("before sort:"+list_1.toString()); Collections.sort(list_1); System.out.println("after sort:"+list_1.toString()); }}

其中创建了一个ArrayList实例去测试sort()方法，执行结果如下：这里写图片描述

开始进入正题，我们首先查看Collections中sort方法的源代码：

public static <T extends Comparable<? super T>> void sort(List<T> list) { list.sort(null);//传入参数还可以是一个Comparator对象，但是也有一定的要求 }

其中牵扯了许多泛型，T表示要排序的序列中的包含类型，这里出现了一个要求，类型 T 必须实现 Comparable 接口,public final class Integer extends Number implements Comparable<Integer>，并且这个接口的类型是 T 或 T 的任一父类。这样声明后，T 的实例之间，T 的实例和它的父类的实例之间，可以相互比较大小。传入的参数为List类型。

这样，我们又开始查看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，此处传入的参数是Object的：

public static void sort(Object[] a) { //如果符合要求，直接对序列进行归并排序操作(legacyMergeSort),最后的归并排序代码可以自己看一下，我就不贴了 //private static void mergeSort(Object[] src,Object[] dest,int low,int high,int off) if (LegacyMergeSort.userRequested) legacyMergeSort(a); else //否则，进入下一环节 ComparableTimSort.sort(a, 0, a.length, null, 0, 0); }

在1.7之后,不再默认使用归并排序，LegacyMergeSort.userRequested被默认为false，也可以通过来更换

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");

所以再再进入ComparableTimSort的sort()，别急，马上就完！传入参数数组a，lo与hi为要执行排序序列的开始与结束位置，work是一个备用的空间，可以为其设置属性，在上面方法的调用中，我们并没有使用到work

static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) { assert a != null && lo >= 0 && lo <= hi && hi <= a.length; int nRemaining = hi - lo; if (nRemaining < 2)//少于2个数字拿来排序，到这里才返回...有毒 return; // 0或1个数字总是排好序的(有点像放屁 if (nRemaining < MIN_MERGE) {//MIN_MERGE的值为32 int initRunLen = countRunAndMakeAscending(a, lo, hi); //大小小于32时，使用二叉排序！ binarySort(a, lo, hi, lo + initRunLen); return; } ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen); int minRun = minRunLength(nRemaining);//minRun值等于长度的一直除以2，直到小于MIN_MERGE do { // Identify next run int runLen = countRunAndMakeAscending(a, lo, hi); // If run is short, extend to min(minRun, nRemaining) if (runLen < minRun) { int force = nRemaining <= minRun ? nRemaining : minRun; binarySort(a, lo, lo + force, lo + runLen); runLen = force; } // Push run onto pending-run stack, and maybe merge ts.pushRun(lo, runLen); ts.mergeCollapse(); // Advance to find next run lo += runLen; nRemaining -= runLen; } while (nRemaining != 0); // Merge all remaining runs to complete sort assert lo == hi; ts.mergeForceCollapse(); assert ts.stackSize == 1; }

其中使用的二分查找与合并等种种过程，根据一个个条件优化操作。精华的地方慢慢品吧。稍后添加！

上一篇：设计模式(3)--观察者模式

下一篇：反射