Collections.sort()方法解析

3/8/2017来源:ASP.NET技巧人气:1397

首先注意这里调用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; }

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