TimSort
timsort是jdk自带的一种特别高效的排序算法,大致思想使用的是归并排序,但是内部细节做了许多的优化.
在timsort中,主要是为待排序数组分为很多个run块,通过讲这些run块进行归并排序.最后实现总体排序.每个run块的大小为16-32大小.
优化地方:
- 当待排序数组长度小于32就使用二分排序算法
- 分为多个run块,在通过把run块的起始位置和长度压入栈中,在进行合并.
- 在找到一个run块的时候会首先判断数组中有序元素的个数.通过二分排序从第一个无序的元素开始排序,加快排序速度
- 在进行合并的时候会进行”去头”,”去尾”操作,是的归并操作加快速度.
sort(T[] a, int lo, int hi, Comparator<? super T> c, T[] work, int workBase, int workLen)
timsort对外的唯一接口.并且只能本包内访问1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46static <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;
int nRemaining = hi - lo;
//小于2不用排序,直接返回
if (nRemaining < 2)
return;
// 看是否小于min_merge,如果小于就直接二分排序,没必要进行复杂的timsort.
if (nRemaining < MIN_MERGE) {
//下面有详细说明.返回的是从lo开始已经有序的个数,对二分排序用
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
// 从第一没有排好序位置开始进行二分排序
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}
//这个时候开始真正的timsort
TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
//主要将数组分为一个个的minRun,最后在进行合并,如果长度为2的n次幂,minRun为32,否则为16-32之间的数.
int minRun = minRunLength(nRemaining);
do {
//再次找到a中已经有序的元素个数
int runLen = countRunAndMakeAscending(a, lo, hi, c);
//如果有序个数小于上面的最小minRun的话,就找到
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen, c);
runLen = force;
}
// 将此run块放入run数组中.
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;
}
minRunLength
就是获得一个最小的Run块的大小,大小在16-32之间.1
2
3
4
5
6
7
8
9private 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;
}
countRunAndMakeAscending(a, lo, hi, c)
找到a数组中从lo开始并且已经有序的元素个数,返回已经有序的元素个数.在这里如果逆序在翻转一下,变为有序.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19private 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;
// 找见a从lo开始已经有序的元素个数
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;
}
binarySort(T[] a, int lo, int hi, int start,Comparator<? super T> c)
此方法就是二分排序,二分排序就是插入排序,但是在寻找向前面插入的位置是通过二分法来查找,然后在插入的.
此方法是在a数组中排序从lo到hi的元素,从start开始.
private void mergeCollapse()
这个方法主要是用来合并已经分好的几个Run块的.但是是有条件的;
- runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
- runLen[i - 2] > runLen[i - 1]
满足这两个条件才合并,否则什么都不做.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17private void mergeCollapse() {
//最少都得有两个块,如果没有,则退出.
while (stackSize > 1) {
int n = stackSize - 2;// stackSize为块的数量,-2相当与倒数第二个块
//如果块的数量大于三个并且倒数第三个Run块大小小于后面两个块的大小和进入
if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
//如果倒数第三个块比倒一块的大小小,就从倒数第三个块进行合并
if (runLen[n - 1] < runLen[n + 1])
n--;
mergeAt(n);
} else if (runLen[n] <= runLen[n + 1]) {//第一个块大小小于第二个块大小,就合并这两个
mergeAt(n);
} else {//否则什么都不做
break; // Invariant is established
}
}
}
private void mergeAt(int i)
再来看mergeAt(i)方法,这个方法主要就是合并在run块数组中从i开始的两个块.run[i]和run[i+1]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35int base1 = runBase[i];
int len1 = runLen[i];
int base2 = runBase[i + 1];
int len2 = runLen[i + 1];
runLen[i] = len1 + len2;
//观察如果是倒数第三个块,就倒数第一个块赋值给倒数第二个块
if (i == stackSize - 3) {
runBase[i + 1] = runBase[i + 2];
runLen[i + 1] = runLen[i + 2];
}
stackSize--;
//计算run2的第一个元素能插入到run1的位置
//如果属于run1的最后一个位置,就不需要排序,因为run1中的所有元素都比run2中的小,直接返回,
//这样可以忽略掉run1中之前的位置
int k = gallopRight(a[base2], a, base1, len1, 0, c);
assert k >= 0;
base1 += k;
len1 -= k;
if (len1 == 0)
return;
//计算run1的最后一个元素在run2中插入的位置,进行去尾.
len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);
assert len2 >= 0;
if (len2 == 0)
return;
// 经过上面的“去头”和“去尾”之后，保证run1的开始元素一定大
// 于run2的开始元素，并且run1的最后一个数据一定大于run2的最后一个数据
// 然后进行合并,通过两个len的大小找到最好的合并方式
if (len1 <= len2)
mergeLo(base1, len1, base2, len2);
else
mergeHi(base1, len1, base2, len2);
private void mergeLo(int base1, int len1, int base2, int len2)
mergeLo方法 合并两个run块1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108 T[] a = this.a; //首先赋值到一个临时数组中
T[] tmp = ensureCapacity(len1);
int cursor1 = tmpBase;
int cursor2 = base2; // Indexes int a
int dest = base1; // Indexes int a
//先吧a从base1开始的元素赋值到tmp从tmpbase开始的元素,赋值len1个元素,因为len1肯定是最小的元素
System.arraycopy(a, base1, tmp, cursor1, len1);
// 首先肯定run2的第一个元素小于run1的第一个元素,因为上面都已经去头了
a[dest++] = a[cursor2++];
if (--len2 == 0) {//如果run2长度为0,则赋值tmp过去,
System.arraycopy(tmp, cursor1, a, dest, len1);
return;
}
if (len1 == 1) {//如果run1只剩下一个元素,所以只需要先把run2复制过去,再讲Run1的唯一元素赋值过去
System.arraycopy(a, cursor2, a, dest, len2);
a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
return;
}
Comparator<? super T> c = this.c; // Use local variable for performance
int minGallop = this.minGallop; // 定义一个最小Gallop
outer: //定义跳出什么循环
//在这里有一个思路就是合并两个run,但是会记录两个块中连续个数的数量,如果连续个数的数量大于minGallop也就是7,那就会进入Gallop模式.此模式就是通过"去头","去尾"来减少比较次数
while (true) {
int count1 = 0; // Number of times in a row that first run won
int count2 = 0; // Number of times in a row that second run won
/*
* Do the straightforward thing until (if ever) one run starts
* winning consistently.
*/
do {
assert len1 > 1 && len2 > 0;
//开始比较
if (c.compare(a[cursor2], tmp[cursor1]) < 0) {
a[dest++] = a[cursor2++];
count2++;
count1 = 0;
if (--len2 == 0)
break outer;
} else {
a[dest++] = tmp[cursor1++];
count1++;
count2 = 0;
if (--len1 == 1)
break outer;
}
//当有一个块有连续大于另一个块的次数超过minGallop的时候,进入gallop模式
} while ((count1 | count2) < minGallop);
/*
* One run is winning so consistently that galloping may be a
* huge win. So try that, and continue galloping until (if ever)
* neither run appears to be winning consistently anymore.
*/
do {
assert len1 > 1 && len2 > 0;
//如上,去掉run1的头部
count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0, c);
if (count1 != 0) {
System.arraycopy(tmp, cursor1, a, dest, count1);
dest += count1;
cursor1 += count1;
len1 -= count1;
if (len1 <= 1) // len1 == 1 || len1 == 0
break outer;
}
a[dest++] = a[cursor2++];
if (--len2 == 0)
break outer;
// 去掉run2的尾部
count2 = gallopLeft(tmp[cursor1], a, cursor2, len2, 0, c);
if (count2 != 0) {
System.arraycopy(a, cursor2, a, dest, count2);
dest += count2;
cursor2 += count2;
len2 -= count2;
if (len2 == 0)
break outer;
}
a[dest++] = tmp[cursor1++];
if (--len1 == 1)
break outer;
minGallop--;
//在此模式每多循环一次minGallop减少1
} while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
if (minGallop < 0)
minGallop = 0;
//在离开这个gallop模式后值增加2
minGallop += 2; // Penalize for leaving gallop mode
} // End of "outer" loop
this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field
if (len1 == 1) {
assert len2 > 0;
System.arraycopy(a, cursor2, a, dest, len2);
a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
} else if (len1 == 0) {
throw new IllegalArgumentException(
"Comparison method violates its general contract!");
} else {
assert len2 == 0;
assert len1 > 1;
//最后将tmp的值赋值到a中
System.arraycopy(tmp, cursor1, a, dest, len1);
}