在jdk中提供了一个集合操作工具类Collections来操作集合。
** 本文基于JDK7 源码进行分析 **
Collections方法列表：
| 方法 | 说明 |
|---|---|
| static <T extends Comparable<? super T>> void sort(List<T> list) | 根据元素的自然顺序 对指定列表按升序进行排序。 要求T必须实现Comparator接口 |
| static <T> void sort(List<T> list, Comparator<? super T> c) | 根据指定比较器产生的顺序对指定列表进行排序。 |
源码
Collections.sort(List<T> list) 方法：
public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator<T> i = list.listIterator();
for (int j=0; j<a.length; j++) {
i.next();
i.set((T)a[j]);
}
}
Collections.sort(List<T> list, Comparator<? super T> c) 方法：
public static <T> void sort(List<T> list, Comparator<? super T> c) {
Object[] a = list.toArray();
Arrays.sort(a, (Comparator)c);
ListIterator i = list.listIterator();
for (int j=0; j<a.length; j++) {
i.next();
i.set(a[j]);
}
}
Collections.sort调用List的toArray函数，将容器转换成Object数组后，再通过Arrays.sort()进行排序；排序完成后再遍历容器，将更新容器中的每个元素值。
Arrays类又是jdk为操作数组提供的一个工具类，里面提供了很多对数组的操作方法，如排序、查找等。
Arrays.sort方法如下：
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, c);
}
/** To be removed in a future release. */
private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) {
T[] aux = a.clone();
if (c==null)
mergeSort(aux, a, 0, a.length, 0);
else
mergeSort(aux, a, 0, a.length, 0, c);
}
mergeSort
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++];
}
}
/**
* Swaps x[a] with x[b].
*/
private static void swap(Object[] x, int a, int b) {
Object t = x[a];
x[a] = x[b];
x[b] = t;
}
单从方法的名字来看就知道是个归并排序，不过又略有不同。
jdk里面对归并做了一个小小的改进，那就是当数组的长度于INSERTIONSORT_THRESHOLD（=7）这个常数的时候使用的是插入排序（Insertion sort ）。
TimSort原理
如果待排序数组长度<32，则使用binarySort，否则使用TimSort：
- 计算minRun（子序列的长度）：
1.1. 若待排数组总长度为2^n，则minRun选取为16；
1.2. 否则，通过将数组长度右移的方式（每次除以2），计算出一个16-32之间的值，作为minRun； - 使用binarySort排序每个子序列；
- 最后用mergeSort对所有的子序列排序；
其中，binarySort是一种插入排序，直接插入排序通过遍历的方式向前搜索插入点，而binarySort通过二分搜索的方式搜索插入点。
过程如下：
- 将待排序列分成两段，前半段为有序序列，后半段为无序序列；
- 每趟在有序序列中为无序序列的第一个元素寻找插入位置，并使用二分搜索的方式寻找；
- 当无序序列长度为0的时候整个排序完成。
TimSort.sort(a)源码如下：
static <T> void sort(T[] a, Comparator<? super T> c) {
sort(a, 0, a.length, c);
}
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c) {
if (c == null) {
Arrays.sort(a, lo, hi);
return;
}
rangeCheck(a.length, lo, hi);
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}
/**
* March over the array once, left to right, finding natural runs,
* extending short natural runs to minRun elements, and merging runs
* to maintain stack invariant.
*/
TimSort<T> ts = new TimSort<>(a, c);
int minRun = minRunLength(nRemaining);
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi, c);
// 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, c);
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;
}
private static <T> void binarySort(T[] a, int lo, int hi, int start,
Comparator<? super T> c) {
assert lo <= start && start <= hi;
if (start == lo)
start++;
for ( ; start < hi; start++) {
T pivot = a[start];
// Set left (and right) to the index where a[start] (pivot) belongs
int left = lo;
int right = start;
assert left <= right;
/*
* Invariants:
* pivot >= all in [lo, left).
* pivot < all in [right, start).
*/
while (left < right) {
int mid = (left + right) >>> 1;
if (c.compare(pivot, a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
assert left == right;
/*
* The invariants still hold: pivot >= all in [lo, left) and
* pivot < all in [left, start), so pivot belongs at left. Note
* that if there are elements equal to pivot, left points to the
* first slot after them -- that's why this sort is stable.
* Slide elements over to make room for pivot.
*/
int n = start - left; // The number of elements to move
// Switch is just an optimization for arraycopy in default case
switch (n) {
case 2: a[left + 2] = a[left + 1];
case 1: a[left + 1] = a[left];
break;
default: System.arraycopy(a, left, a, left + 1, n);
}
a[left] = pivot;
}
}
网友评论