Arrays源码详解

110 阅读 0 评论 73 点赞

我是靠谱客的博主激昂荔枝，这篇文章主要介绍Arrays源码详解，现在分享给大家，希望可以做个参考。

此类包含用于操作数组的各种方法（例如排序和搜索）。这个类还包含一个静态工厂，允许将数组视为列表。

一、继承关系图

一个工具类，没有继承关系

二、Arrays类介绍

复制代码

1
2
private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;

最小并行排序数组，低于该长度将不会采用并行计算排序。

复制代码

1
2
3
4
5
6
7
8
static final class NaturalOrder implements Comparator<Object> {
@SuppressWarnings("unchecked")
public int compare(Object first, Object second) {
return ((Comparable<Object>)first).compareTo(second);
}
static final NaturalOrder INSTANCE = new NaturalOrder();
}

定义一个比较器类。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
if (fromIndex > toIndex) {
throw new IllegalArgumentException(
"fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
}
if (fromIndex < 0) {
throw new ArrayIndexOutOfBoundsException(fromIndex);
}
if (toIndex > arrayLength) {
throw new ArrayIndexOutOfBoundsException(toIndex);
}
}

范围判断。

复制代码

public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(int[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
public static void sort(long[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(long[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
public static void sort(short[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(short[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
public static void sort(char[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(char[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
public static void sort(byte[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1);
}
public static void sort(byte[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
}
public static void sort(float[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(float[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
public static void sort(double[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(double[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}

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
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(int[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
public static void sort(long[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(long[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
public static void sort(short[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(short[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
public static void sort(char[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(char[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
public static void sort(byte[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1);
}
public static void sort(byte[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
}
public static void sort(float[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(float[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
public static void sort(double[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(double[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}

当排序数组大小小于286时使用普通快排，否则使用双轴快排，双轴快排每次选择两个数a < b，然后将数据根据小于等于a，大于a小于b，大于等于b来分为三组，依次递归。（但是它是使用非递归实现的）。

复制代码

public static void parallelSort(byte[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1);
else
new ArraysParallelSortHelpers.FJByte.Sorter
(null, a, new byte[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(byte[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
else
new ArraysParallelSortHelpers.FJByte.Sorter
(null, a, new byte[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(char[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJChar.Sorter
(null, a, new char[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(char[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJChar.Sorter
(null, a, new char[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(short[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJShort.Sorter
(null, a, new short[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(short[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJShort.Sorter
(null, a, new short[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(int[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJInt.Sorter
(null, a, new int[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(int[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJInt.Sorter
(null, a, new int[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(long[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJLong.Sorter
(null, a, new long[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(long[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJLong.Sorter
(null, a, new long[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(float[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJFloat.Sorter
(null, a, new float[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(float[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJFloat.Sorter
(null, a, new float[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(double[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJDouble.Sorter
(null, a, new double[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(double[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJDouble.Sorter
(null, a, new double[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static <T extends Comparable<? super T>> void parallelSort(T[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, 0, n, NaturalOrder.INSTANCE, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[])Array.newInstance(a.getClass().getComponentType(), n),
0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke();
}
public static <T extends Comparable<? super T>>
void parallelSort(T[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, fromIndex, toIndex, NaturalOrder.INSTANCE, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[])Array.newInstance(a.getClass().getComponentType(), n),
fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke();
}
public static <T> void parallelSort(T[] a, Comparator<? super T> cmp) {
if (cmp == null)
cmp = NaturalOrder.INSTANCE;
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, 0, n, cmp, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[])Array.newInstance(a.getClass().getComponentType(), n),
0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
}
public static <T> void parallelSort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> cmp) {
rangeCheck(a.length, fromIndex, toIndex);
if (cmp == null)
cmp = NaturalOrder.INSTANCE;
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, fromIndex, toIndex, cmp, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[])Array.newInstance(a.getClass().getComponentType(), n),
fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
}

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
public static void parallelSort(byte[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1);
else
new ArraysParallelSortHelpers.FJByte.Sorter
(null, a, new byte[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(byte[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
else
new ArraysParallelSortHelpers.FJByte.Sorter
(null, a, new byte[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(char[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJChar.Sorter
(null, a, new char[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(char[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJChar.Sorter
(null, a, new char[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(short[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJShort.Sorter
(null, a, new short[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(short[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJShort.Sorter
(null, a, new short[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(int[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJInt.Sorter
(null, a, new int[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(int[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJInt.Sorter
(null, a, new int[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(long[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJLong.Sorter
(null, a, new long[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(long[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJLong.Sorter
(null, a, new long[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(float[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJFloat.Sorter
(null, a, new float[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(float[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJFloat.Sorter
(null, a, new float[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(double[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJDouble.Sorter
(null, a, new double[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(double[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJDouble.Sorter
(null, a, new double[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static <T extends Comparable<? super T>> void parallelSort(T[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, 0, n, NaturalOrder.INSTANCE, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[])Array.newInstance(a.getClass().getComponentType(), n),
0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke();
}
public static <T extends Comparable<? super T>>
void parallelSort(T[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, fromIndex, toIndex, NaturalOrder.INSTANCE, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[])Array.newInstance(a.getClass().getComponentType(), n),
fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke();
}
public static <T> void parallelSort(T[] a, Comparator<? super T> cmp) {
if (cmp == null)
cmp = NaturalOrder.INSTANCE;
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, 0, n, cmp, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[])Array.newInstance(a.getClass().getComponentType(), n),
0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
}
public static <T> void parallelSort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> cmp) {
rangeCheck(a.length, fromIndex, toIndex);
if (cmp == null)
cmp = NaturalOrder.INSTANCE;
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, fromIndex, toIndex, cmp, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[])Array.newInstance(a.getClass().getComponentType(), n),
fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
}

并行计算框架，如果数组大小雄鱼8196就使用Arrays.sort方法，否则就将数组分为多个长度不大于8196的数组使用多线程将每个数组调用Arrays.sort方法进行排序，之后对排序后的数组进行合并。

复制代码

public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
/**
* Old merge sort implementation can be selected (for
* compatibility with broken comparators) using a system property.
* Cannot be a static boolean in the enclosing class due to
* circular dependencies. To be removed in a future release.
*/
static final class LegacyMergeSort {
private static final boolean userRequested =
java.security.AccessController.doPrivileged(
new sun.security.action.GetBooleanAction(
"java.util.Arrays.useLegacyMergeSort")).booleanValue();
}
private static void legacyMergeSort(Object[] a) {
Object[] aux = a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
public static void sort(Object[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex);
else
ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
}
private static void legacyMergeSort(Object[] a,
int fromIndex, int toIndex) {
Object[] aux = copyOfRange(a, fromIndex, toIndex);
mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
}

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
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
/**
* Old merge sort implementation can be selected (for
* compatibility with broken comparators) using a system property.
* Cannot be a static boolean in the enclosing class due to
* circular dependencies. To be removed in a future release.
*/
static final class LegacyMergeSort {
private static final boolean userRequested =
java.security.AccessController.doPrivileged(
new sun.security.action.GetBooleanAction(
"java.util.Arrays.useLegacyMergeSort")).booleanValue();
}
private static void legacyMergeSort(Object[] a) {
Object[] aux = a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
public static void sort(Object[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex);
else
ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
}
private static void legacyMergeSort(Object[] a,
int fromIndex, int toIndex) {
Object[] aux = copyOfRange(a, fromIndex, toIndex);
mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
}

LegacyMergeSort在以后的JDK版本会抛弃，ComarableTimSort方法对归并排序进行了优化，对归并排序排在已经反向排好序的输入时表现O(n2)的特点做了特别优化。对已经正向排好序的输入降低回溯。对两种情况混合（一会升序。一会降序）的输入处理比较好。

复制代码

1
2
3
4
5
6
private static void swap(Object[] x, int a, int b) {
Object t = x[a];
x[a] = x[b];
x[b] = t;
}

交换数组中两元素。

复制代码

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
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);
}
}
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);
}
public static <T> void sort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c) {
if (c == null) {
sort(a, fromIndex, toIndex);
} else {
rangeCheck(a.length, fromIndex, toIndex);
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex, c);
else
TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
}
}
private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c) {
T[] aux = copyOfRange(a, fromIndex, toIndex);
if (c==null)
mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
else
mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
}

复制代码

public static <T> void parallelPrefix(T[] array, BinaryOperator<T> op) {
Objects.requireNonNull(op);
if (array.length > 0)
new ArrayPrefixHelpers.CumulateTask<>
(null, op, array, 0, array.length).invoke();
}
public static <T> void parallelPrefix(T[] array, int fromIndex,
int toIndex, BinaryOperator<T> op) {
Objects.requireNonNull(op);
rangeCheck(array.length, fromIndex, toIndex);
if (fromIndex < toIndex)
new ArrayPrefixHelpers.CumulateTask<>
(null, op, array, fromIndex, toIndex).invoke();
}
public static void parallelPrefix(long[] array, LongBinaryOperator op) {
Objects.requireNonNull(op);
if (array.length > 0)
new ArrayPrefixHelpers.LongCumulateTask
(null, op, array, 0, array.length).invoke();
}
public static void parallelPrefix(long[] array, int fromIndex,
int toIndex, LongBinaryOperator op) {
Objects.requireNonNull(op);
rangeCheck(array.length, fromIndex, toIndex);
if (fromIndex < toIndex)
new ArrayPrefixHelpers.LongCumulateTask
(null, op, array, fromIndex, toIndex).invoke();
}
public static void parallelPrefix(double[] array, DoubleBinaryOperator op) {
Objects.requireNonNull(op);
if (array.length > 0)
new ArrayPrefixHelpers.DoubleCumulateTask
(null, op, array, 0, array.length).invoke();
}
public static void parallelPrefix(double[] array, int fromIndex,
int toIndex, DoubleBinaryOperator op) {
Objects.requireNonNull(op);
rangeCheck(array.length, fromIndex, toIndex);
if (fromIndex < toIndex)
new ArrayPrefixHelpers.DoubleCumulateTask
(null, op, array, fromIndex, toIndex).invoke();
}
public static void parallelPrefix(int[] array, IntBinaryOperator op) {
Objects.requireNonNull(op);
if (array.length > 0)
new ArrayPrefixHelpers.IntCumulateTask
(null, op, array, 0, array.length).invoke();
}
public static void parallelPrefix(int[] array, int fromIndex,
int toIndex, IntBinaryOperator op) {
Objects.requireNonNull(op);
rangeCheck(array.length, fromIndex, toIndex);
if (fromIndex < toIndex)
new ArrayPrefixHelpers.IntCumulateTask
(null, op, array, fromIndex, toIndex).invoke();
}

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
public static <T> void parallelPrefix(T[] array, BinaryOperator<T> op) {
Objects.requireNonNull(op);
if (array.length > 0)
new ArrayPrefixHelpers.CumulateTask<>
(null, op, array, 0, array.length).invoke();
}
public static <T> void parallelPrefix(T[] array, int fromIndex,
int toIndex, BinaryOperator<T> op) {
Objects.requireNonNull(op);
rangeCheck(array.length, fromIndex, toIndex);
if (fromIndex < toIndex)
new ArrayPrefixHelpers.CumulateTask<>
(null, op, array, fromIndex, toIndex).invoke();
}
public static void parallelPrefix(long[] array, LongBinaryOperator op) {
Objects.requireNonNull(op);
if (array.length > 0)
new ArrayPrefixHelpers.LongCumulateTask
(null, op, array, 0, array.length).invoke();
}
public static void parallelPrefix(long[] array, int fromIndex,
int toIndex, LongBinaryOperator op) {
Objects.requireNonNull(op);
rangeCheck(array.length, fromIndex, toIndex);
if (fromIndex < toIndex)
new ArrayPrefixHelpers.LongCumulateTask
(null, op, array, fromIndex, toIndex).invoke();
}
public static void parallelPrefix(double[] array, DoubleBinaryOperator op) {
Objects.requireNonNull(op);
if (array.length > 0)
new ArrayPrefixHelpers.DoubleCumulateTask
(null, op, array, 0, array.length).invoke();
}
public static void parallelPrefix(double[] array, int fromIndex,
int toIndex, DoubleBinaryOperator op) {
Objects.requireNonNull(op);
rangeCheck(array.length, fromIndex, toIndex);
if (fromIndex < toIndex)
new ArrayPrefixHelpers.DoubleCumulateTask
(null, op, array, fromIndex, toIndex).invoke();
}
public static void parallelPrefix(int[] array, IntBinaryOperator op) {
Objects.requireNonNull(op);
if (array.length > 0)
new ArrayPrefixHelpers.IntCumulateTask
(null, op, array, 0, array.length).invoke();
}
public static void parallelPrefix(int[] array, int fromIndex,
int toIndex, IntBinaryOperator op) {
Objects.requireNonNull(op);
rangeCheck(array.length, fromIndex, toIndex);
if (fromIndex < toIndex)
new ArrayPrefixHelpers.IntCumulateTask
(null, op, array, fromIndex, toIndex).invoke();
}

使用提供的函数并行累积给定数组的每个元素。例如，如果数组最初保存[2, 1, 0, 3]并且该操作执行加法，则在返回时数组保存[2, 3, 3, 6] 。对于大型数组，并行前缀计算通常比顺序循环更有效。

复制代码

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
public static int binarySearch(long[] a, long key) {
return binarySearch0(a, 0, a.length, key);
}
public static int binarySearch(long[] a, int fromIndex, int toIndex,
long key) {
rangeCheck(a.length, fromIndex, toIndex);
return binarySearch0(a, fromIndex, toIndex, key);
}
public static int binarySearch(int[] a, int key) {
return binarySearch0(a, 0, a.length, key);
}
public static int binarySearch(int[] a, int fromIndex, int toIndex,
int key) {
rangeCheck(a.length, fromIndex, toIndex);
return binarySearch0(a, fromIndex, toIndex, key);
}
private static int binarySearch0(long[] a, int fromIndex, int toIndex,
long key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
long midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1);
// key not found.
}

二分查找指定值的下标。找不到返回-1。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static boolean equals(long[] a, long[] a2) {
if (a==a2)
return true;
if (a==null || a2==null)
return false;
int length = a.length;
if (a2.length != length)
return false;
for (int i=0; i<length; i++)
if (a[i] != a2[i])
return false;
return true;
}

比较两个数组元素是否相同。

复制代码

1
2
3
4
5
public static void fill(long[] a, long val) {
for (int i = 0, len = a.length; i < len; i++)
a[i] = val;
}

将数组中元素全部填充为val。

复制代码

1
2
3
4
5
6
7
8
9
10
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}

复制一份新的数组返回。

复制代码

1
2
3
4
5
6
7
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
private static class ArrayList<E> extends AbstractList<E>
implements RandomAccess, java.io.Serializable
{

返回一个列表，注意返回这个列表不是我们常用的ArrayList，它是一个内部类，我们接收的时候会使用List去接受。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int hashCode(long a[]) {
if (a == null)
return 0;
int result = 1;
for (long element : a) {
int elementHash = (int)(element ^ (element >>> 32));
result = 31 * result + elementHash;
}
return result;
}
public static int hashCode(int a[]) {
if (a == null)
return 0;
int result = 1;
for (int element : a)
result = 31 * result + element;
return result;
}

获取hashCode值。

复制代码

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
public static int deepHashCode(Object a[]) {
if (a == null)
return 0;
int result = 1;
for (Object element : a) {
int elementHash = 0;
if (element instanceof Object[])
elementHash = deepHashCode((Object[]) element);
else if (element instanceof byte[])
elementHash = hashCode((byte[]) element);
else if (element instanceof short[])
elementHash = hashCode((short[]) element);
else if (element instanceof int[])
elementHash = hashCode((int[]) element);
else if (element instanceof long[])
elementHash = hashCode((long[]) element);
else if (element instanceof char[])
elementHash = hashCode((char[]) element);
else if (element instanceof float[])
elementHash = hashCode((float[]) element);
else if (element instanceof double[])
elementHash = hashCode((double[]) element);
else if (element instanceof boolean[])
elementHash = hashCode((boolean[]) element);
else if (element != null)
elementHash = element.hashCode();
result = 31 * result + elementHash;
}
return result;
}

获取深度hashCode值，就是当数组中的元素是数组类型就接着调用hashCOde方法。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static boolean deepEquals(Object[] a1, Object[] a2) {
if (a1 == a2)
return true;
if (a1 == null || a2==null)
return false;
int length = a1.length;
if (a2.length != length)
return false;
for (int i = 0; i < length; i++) {
Object e1 = a1[i];
Object e2 = a2[i];
if (e1 == e2)
continue;
if (e1 == null)
return false;
// Figure out whether the two elements are equal
boolean eq = deepEquals0(e1, e2);
if (!eq)
return false;
}
return true;
}