Collections.sort()：是对一个集合进行正向排序的方法
首先，传入Collections.sort()的集合的元素类型要继承Comparator<T>,这样才能保证可以比较并排序。
下面举个例子，我要正序排列100,50,70,60这四个数字，代码如下：
List<Integer> result = new ArrayList<Integer>(){{add(100);add(50);add(70);add(60);}};
Collections.sort(result);
for (Integer integer : result) {
System.out.println(integer);
}
}
进到 Collections.sort（）方法中：
public static <T extends Comparable<? super T>> void sort(List<T> list) {
list.sort(null);
}
因为没有传入Comparable对象，所以 list.sort(null);中为null
接着往下走：
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);
}
}
可以看到，在 list.sort()方法中，将传进来的List集合转换成了一个Object数组，
接着调用Arrays.sort()方法，进到里面看一下，
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a);
} else {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}
这里有一个分支：
LegacyMergeSort.userRequested：百度一下-用户请求传统归并排序，这个方法不做讨论，除非用户特殊要求，一般会走另一个分支：TimSort.sort（）
这个就是整个排序的方法了：
* @param a the array to be sorted 排序的数字
* @param lo the index of the first element, inclusive, to be sorted 要排序的第一个元素（包括）的索引
* @param hi the index of the last element, exclusive, to be sorted 要排序的最后一个元素（不含）的索引
* @param c the comparator to use 参数c要使用的比较器
* @param work a workspace array (slice) 参数工作区数组（切片）
* @param workBase origin of usable space in work array 工作数组中可用空间的参数WorkBase原点
* @param workLen usable size of work array 工作阵列的参数工作状态可用大小
* MIN_MERGE = 32;
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
T[] work, int workBase, int workLen) {
// 有一些基本的判断，
assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
// 如果数组中只有0或者1个元素，则不需要排序了
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
// 如果数组很小（小于32个元素），调用不包含合并操作的mini-TimSort
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对象
TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
int minRun = minRunLength(nRemaining);
do {
// Identify next run
////跟二叉查找插入排序一样，先找自然升序序列
int runLen = countRunAndMakeAscending(a, lo, hi, c);
// If run is short, extend to min(minRun, nRemaining)
// // 如果 自然升序的长度不够minRun，就把 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
//把指针后移runLen距离，准备开始下一轮片段的排序
lo += runLen;
//剩下待排序的数量相应的减少 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> int countRunAndMakeAscending(T[] a, int lo, int hi,
Comparator<? super T> c) {
assert lo < hi;
int runHi = lo + 1;
if (runHi == hi)
return 1;
// Find end of run, and reverse range if descending
//从数组开始处找到一组连接升序的数
if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
runHi++;
reverseRange(a, lo, runHi);
// 从数组开始处找到一组严格降序（找到后翻转）的数
} else { // Ascending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
runHi++;
}
// 返回这个数值的位置
return runHi - lo;
}
解释一下用到的第二个方法：
Binary Sort：使用二分查找的方法将后续的数插入之前的已排序数组，binarySort 对数组 a[lo:hi] 进行排序，并且a[lo:start] 是已经排好序的。算法的思路是对a[start:hi] 中的元素，每次使用binarySearch 为它在a[lo:start] 中找到相应位置，并插入。
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
//控制要排序元素的区间，最左是lo,最右是start
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)
//如果pivot比中间数的值小，最右的下标变成中间数的下标，相当于去掉数组的右半部分
right = mid;
else
//最左的下标变成中间数的下标，相当于去掉数组的左半部分
left = mid + 1;
}
//直到最右下标相等，找到 pivot可以插入的位置
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.
*/
// 插入point
// 需要移动的范围的长度
int n = start - left; // The number of elements to move
// Switch is just an optimization for arraycopy in default case
//1-2个元素的移动就不需要System.arraycopy了
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;
}
}
解释一下用到的第三个方法：
private static int minRunLength(int n) {
assert n >= 0;
int r = 0; // Becomes 1 if any 1 bits are shifted off
while (n >= MIN_MERGE) {
r |= (n & 1);
n >>= 1;
}
return n + r;
}
a) 如果数组大小为2的N次幂，则返回16（MIN_MERGE / 2）
b) 其他情况下，逐位向右位移（即除以2），直到找到介于16和32间的一个数。这个函数根据 n 计算出对应的 natural run 的最小长度。MIN_MERGE 默认为32，如果n小于此值，那么返回n 本身。否则会将 n 不断地右移，直到少于 MIN_MERGE，同时记录一个 r 值，r 代表最后一次移位n时，n最低位是0还是1。 最后返回 n + r，这也意味着只保留最高的 5 位，再加上第六位
网友评论