MyException - 我的异常网
当前位置:我的异常网» 编程 » Collections源码sort步骤解读

Collections源码sort步骤解读

www.MyException.Cn  网友分享于:2013-12-26  浏览:4次
Collections源码sort方法解读

首先看jdk1.5源码中的Collections.java中的sort方法源码:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
	(1):Object[] a = list.toArray();
	(2):Arrays.sort(a);    
	(3):ListIterator<T> i = list.listIterator();
	      for (int j=0; j<a.length; j++) {
	           i.next();
	           i.set((T)a[j]);
	       }
 }

这个方法的定义:<T extends Comparable<? super T>> 表示该方法中传递的泛型参数必须实现了Comparable中的compareTo(T o)方法,否则进行不了sort排序。

把这个方法细分为3个步骤:

(1)将list装换成一个对象数组

(2)将这个对象数组传递给Arrays类的sort方法(也就是说collections的sort其实本质是调用了Arrays.sort)

(3)通过(2)步骤排好序后指定list的iterator位置,返回一个排好序的list

 

然后进入Arrays.java查看sort源代码:

 

public static void sort(Object[] a) {
        Object[] aux = (Object[])a.clone();
        mergeSort(aux, a, 0, a.length, 0);
}

 很显然主要的排序方法是private static void mergeSort(Object[] src, Object[] dest,int low,int high, int off)

方法原理为:

  根据指定比较器产生的顺序对指定对象数组的指定范围进行排序。排序的范围从索引 low(包括)一直到索引 high(不包括)。(如果 low==high,则排序范围为空。)此范围内的所有元素都必须是通过指定比较器可相互比较的(也就是说,对于该范围中的任何 e1 和 e2 元素而言,c.compare(e1, e2) 不得抛出 ClassCastException)。因此也就是前面提到的必须实现Comparable中的compareTo(T o)方法。

 

最后进入sort核心排序算法mergeSort源代码:

private static void mergeSort(Object[] src,Object[] dest,
				  int low,int high,int off) {
	int length = high - low;

	// Insertion sort on smallest arrays
   ①  if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
			 ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

        // Recursively sort halves of dest into src
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >> 1;
   ②  mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
   ③  if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
    ④  for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid   &&((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

 ①:这个方法接收Object[] src,Object[] dest两个数组,根据调用它的方法可以看出只需要对dest[]这个数组中的元素

       进行排序后,传递过来的List<T> list也即排好了序,src[]数组用来进行中介的,也即后面的方法需要调用(所以

      这两个数组必须区分作用),这里有个判断条件为length < INSERTIONSORT_THRESHOLD,

      INSERTIONSORT_THRESHOLD为Arrays的一个常量为7,它定义了如果数组元素小于7的话就直接用swap方法

      排序,提高了程序的执行效率。

 

 ②:当数组元素大于7的时候,程序先将数组拆分成低区间和高区间两个区间,再调用两个递归对这两个区间元素进行排

       序。在递归时还得判断已经划分的区间元素是否还多于7位,如果多于7位的话继续划分成两个区间,这样循环递归调

       用。在这个方法中,要特别注意src[]和dest[]的参数传递位置,调用递归方法时,是将src[]数组作为排序对象进行排

       序,src[]排序后,在通过③或④方法将dest[]数组依据src进行排序。最终达到List<T> list排序的结果。

 

  ③:如果初始元素个数大于等于7个的话(小于7的直接在①方法排好序返回)进过②方法后,只有两种情况:两个排好序

       的低区间和高区间。这个方法作用是:如果低区间列表中的最高元素小于高区间列表中的最低元素,则表明该次递归

       循环的区间段已经排好序,然后将这段数据复制到dest[]数组中。反之则进入方法④。

 

   ④:进入该方法表明该次递归循环的低区间的数字最高元素大于高区间列表中的最低元素,也就是说低区间的数组元素值

         都大于高区间的数组元素值,因此将src中的高区间元素和低区间元素调换放入dest数组中。这样一次递归循环就调

         用完毕,如果还有循环就继续排序下去,否则排序就已经完成。

 

 闲来无事写下这个排序的笔记,作为以后忘记时的参考!!

 

 

 

 

 

文章评论

程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
编程语言是女人
编程语言是女人
程序员的鄙视链
程序员的鄙视链
旅行,写作,编程
旅行,写作,编程
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
一个程序员的时间管理
一个程序员的时间管理
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员必看的十大电影
程序员必看的十大电影
代码女神横空出世
代码女神横空出世
如何成为一名黑客
如何成为一名黑客
我是如何打败拖延症的
我是如何打败拖延症的
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
漫画:程序员的工作
漫画:程序员的工作
我的丈夫是个程序员
我的丈夫是个程序员
程序员都该阅读的书
程序员都该阅读的书
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
中美印日四国程序员比较
中美印日四国程序员比较
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
那些争议最大的编程观点
那些争议最大的编程观点
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员和编码员之间的区别
程序员和编码员之间的区别
每天工作4小时的程序员
每天工作4小时的程序员
 程序员的样子
程序员的样子
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
老程序员的下场
老程序员的下场
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
鲜为人知的编程真相
鲜为人知的编程真相
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
程序员应该关注的一些事儿
程序员应该关注的一些事儿
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有