首先看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数组中。这样一次递归循环就调
用完毕,如果还有循环就继续排序下去,否则排序就已经完成。
闲来无事写下这个排序的笔记,作为以后忘记时的参考!!
分享到:
相关推荐
在Java编程中,`List`接口是集合框架的重要组成部分,提供了有序的元素存储。...通过阅读和理解`Collections.sort()`的源码,开发者可以进一步提升自己的技能,同时也能更好地理解和运用其他Java集合框架的方法。
在Java编程语言中,`Collections.shuffle()`方法是一个非常实用的工具,它用于对集合中的元素进行随机排序。这个方法在处理各种数据集时,比如游戏中打乱卡片顺序、抽奖程序或者任何需要随机化顺序的场景,都发挥着...
Java中的Collections.sort排序是Java.util.Collections类中的一个静态方法,用于对列表进行排序。下面将详细介绍Collections.sort排序的使用和实现机制。 Collections.sort()方法的使用: Collections.sort()方法...
Java Collections.sort()实现List排序的默认方法和自定义方法 Java Collections.sort()是Java语言中用于对List进行排序的方法,通过使用这个方法可以对List进行默认排序,也可以根据需要实现自定义的排序规则。 ...
在Java编程语言中,`Collections.sort()`方法是一个非常重要的工具,它用于对集合中的元素进行排序。这个方法主要应用于`List`接口的实现类,如`ArrayList`和`LinkedList`等。`Collections.sort()`有两种主要的排序...
首先,`Collections.sort()`方法在处理列表(List)时,实际上底层调用了`list.sort()`方法。在Java中,`List`是一个接口,具体的实现类如`ArrayList`或`LinkedList`会提供具体的排序实现。在本例中,由于使用了`...
在Java编程中,集合框架是处理数据的重要工具,而Collections.sort方法则是对列表(List)进行排序的关键函数。本文将深入探讨两种使用Collections.sort方法对List排序的方法。 首先,第一种方法是让List中的对象实现...
Collections.sort 方法的第二个参数形式是 public static <T> void sort(List<T> list, Comparator<? super T> c),该方法允许我们通过实现 Comparator 接口的 compare 方法来完成自定义排序。 下面是一个使用...
在Java编程语言中,`Collections.sort()` 方法是一个非常重要的工具,用于对List接口实现的集合进行排序。这个方法使得开发者能够方便地按照指定的顺序排列集合中的元素。本篇文章将详细探讨如何使用 `Collections....
《Apache Commons Collections 3.2源码解析》 Apache Commons Collections是Java开发中不可或缺的工具库,它极大地扩展了Java的内置集合框架,为开发者提供了更丰富的数据结构和算法实现。这个源码包,名为"commons...
在Java编程语言中,`Collections.sort()` 是一个非常重要的函数,它用于对集合中的元素进行排序。这个函数是 `java.util.Collections` 类的一个静态方法,适用于列表(List)类型的集合。`Collections.sort()` 可以...
在 Java 中,Collections.sort() 方法是排序算法的核心方法,该方法可以对列表进行排序。 SORT() 方法可以对列表进行自然排序,也可以根据 Comparator 对象对列表进行自定义排序。 在本文中,我们将使用 Java ...
Collections 是 Java 中的一个集合工具类,提供了多种操作集合的方法。下面是对 Collections 中部分方法的详细解释。 概述 Collections 类是一个集合工具类,它提供了多种操作集合的方法,如查找、排序、线程安全...
在Java编程中,Collections工具类提供了许多方便的集合操作,其中`sort()`方法是一个非常重要的功能,用于对List类型的集合进行排序。本文将详细介绍`Collections.sort()`方法的两种使用方式及其示例。 ### 一、...
10-集合(Collections-sort).avi
首先,Collections工具类提供了一些通用的操作方法,例如`sort()`,它可以对List进行排序。`sort(List<T> list)`方法使用自然顺序对指定列表进行排序,如果列表元素是自定义类型,那么需要实现Comparable接口来定义...
深入阅读`Collections`源码,我们可以看到这些方法是如何利用Java集合框架的底层实现来提供高效且功能丰富的服务的。比如,`sort()`方法的实现依赖于`Comparable`接口或`Comparator`接口,而`binarySearch()`则需要...
Collections 源码 java jdk1.8-source-analysis JDK1.8源码分析 导入源码过程中的注意事项 JDK1.8对应JDK版本下载: 提取码:49wi 源码在src目录下 以下两个类手动添加的,解决编译过程中该包的丢失 sun.font....
Arkts的源码包是专为开发者提供的一个项目,它采用了Deveco Studio作为其主要的编译工具。Deveco Studio是一款强大的集成开发环境(IDE),尤其在处理特定类型的软件开发时,如企业级应用或者特定领域的软件,它提供...