java Arrays.sort源码解读

1
public static void sort(int[] a) {
2
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
3
}

1
static void sort(int[] a, int left, int right, int[] work, int workBase, int workLen) {
2
    // Use Quicksort on small arrays
3
    if (right - left < QUICKSORT_THRESHOLD) {
4
        sort(a, left, right, true);
5
        return;
6
    }
7

8
    /*
9
        * Index run[i] is the start of i-th run
10
        * (ascending or descending sequence).
11
        */
12
    int[] run = new int[MAX_RUN_COUNT + 1];
13
    int count = 0; run[0] = left;
14

15
    // Check if the array is nearly sorted
82 collapsed lines
16
    for (int k = left; k < right; run[count] = k) {
17
        if (a[k] < a[k + 1]) { // ascending
18
            while (++k <= right && a[k - 1] <= a[k]);
19
        } else if (a[k] > a[k + 1]) { // descending
20
            while (++k <= right && a[k - 1] >= a[k]);
21
            for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
22
                int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
23
            }
24
        } else { // equal
25
            for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
26
                if (--m == 0) {
27
                    sort(a, left, right, true);
28
                    return;
29
                }
30
            }
31
        }
32

33
        /*
34
            * The array is not highly structured,
35
            * use Quicksort instead of merge sort.
36
            */
37
        if (++count == MAX_RUN_COUNT) {
38
            sort(a, left, right, true);
39
            return;
40
        }
41
    }
42

43
    // Check special cases
44
    // Implementation note: variable "right" is increased by 1.
45
    if (run[count] == right++) { // The last run contains one element
46
        run[++count] = right;
47
    } else if (count == 1) { // The array is already sorted
48
        return;
49
    }
50

51
    // Determine alternation base for merge
52
    byte odd = 0;
53
    for (int n = 1; (n <<= 1) < count; odd ^= 1);
54

55
    // Use or create temporary array b for merging
56
    int[] b;                 // temp array; alternates with a
57
    int ao, bo;              // array offsets from 'left'
58
    int blen = right - left; // space needed for b
59
    if (work == null || workLen < blen || workBase + blen > work.length) {
60
        work = new int[blen];
61
        workBase = 0;
62
    }
63
    if (odd == 0) {
64
        System.arraycopy(a, left, work, workBase, blen);
65
        b = a;
66
        bo = 0;
67
        a = work;
68
        ao = workBase - left;
69
    } else {
70
        b = work;
71
        ao = 0;
72
        bo = workBase - left;
73
    }
74

75
    // Merging
76
    for (int last; count > 1; count = last) {
77
        for (int k = (last = 0) + 2; k <= count; k += 2) {
78
            int hi = run[k], mi = run[k - 1];
79
            for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
80
                if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
81
                    b[i + bo] = a[p++ + ao];
82
                } else {
83
                    b[i + bo] = a[q++ + ao];
84
                }
85
            }
86
            run[++last] = hi;
87
        }
88
        if ((count & 1) != 0) {
89
            for (int i = right, lo = run[count - 1]; --i >= lo;
90
                b[i + bo] = a[i + ao]
91
            );
92
            run[++last] = right;
93
        }
94
        int[] t = a; a = b; b = t;
95
        int o = ao; ao = bo; bo = o;
96
    }
97
}

1
 // Use Quicksort on small arrays
2
if (right - left < QUICKSORT_THRESHOLD) {
3
    sort(a, left, right, true);
4
    return;
5
}

1
private static void sort(int[] a, int left, int right, boolean leftmost) {
2
    int length = right - left + 1;
3

4
    // Use insertion sort on tiny arrays
5
    if (length < INSERTION_SORT_THRESHOLD) {
6
        if (leftmost) {
7
            /*
8
                * Traditional (without sentinel) insertion sort,
9
                * optimized for server VM, is used in case of
10
                * the leftmost part.
11
                */
12
            for (int i = left, j = i; i < right; j = ++i) {
13
                int ai = a[i + 1];
14
                while (ai < a[j]) {
15
                    a[j + 1] = a[j];
314 collapsed lines
16
                    if (j-- == left) {
17
                        break;
18
                    }
19
                }
20
                a[j + 1] = ai;
21
            }
22
        } else {
23
            /*
24
                * Skip the longest ascending sequence.
25
                */
26
            do {
27
                if (left >= right) {
28
                    return;
29
                }
30
            } while (a[++left] >= a[left - 1]);
31

32
            /*
33
                * Every element from adjoining part plays the role
34
                * of sentinel, therefore this allows us to avoid the
35
                * left range check on each iteration. Moreover, we use
36
                * the more optimized algorithm, so called pair insertion
37
                * sort, which is faster (in the context of Quicksort)
38
                * than traditional implementation of insertion sort.
39
                */
40
            for (int k = left; ++left <= right; k = ++left) {
41
                int a1 = a[k], a2 = a[left];
42

43
                if (a1 < a2) {
44
                    a2 = a1; a1 = a[left];
45
                }
46
                while (a1 < a[--k]) {
47
                    a[k + 2] = a[k];
48
                }
49
                a[++k + 1] = a1;
50

51
                while (a2 < a[--k]) {
52
                    a[k + 1] = a[k];
53
                }
54
                a[k + 1] = a2;
55
            }
56
            int last = a[right];
57

58
            while (last < a[--right]) {
59
                a[right + 1] = a[right];
60
            }
61
            a[right + 1] = last;
62
        }
63
        return;
64
    }
65

66
    // Inexpensive approximation of length / 7
67
    int seventh = (length >> 3) + (length >> 6) + 1;
68

69
    /*
70
        * Sort five evenly spaced elements around (and including) the
71
        * center element in the range. These elements will be used for
72
        * pivot selection as described below. The choice for spacing
73
        * these elements was empirically determined to work well on
74
        * a wide variety of inputs.
75
        */
76
    int e3 = (left + right) >>> 1; // The midpoint
77
    int e2 = e3 - seventh;
78
    int e1 = e2 - seventh;
79
    int e4 = e3 + seventh;
80
    int e5 = e4 + seventh;
81

82
    // Sort these elements using insertion sort
83
    if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
84

85
    if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
86
        if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
87
    }
88
    if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
89
        if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
90
            if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
91
        }
92
    }
93
    if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
94
        if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
95
            if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
96
                if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
97
            }
98
        }
99
    }
100

101
    // Pointers
102
    int less  = left;  // The index of the first element of center part
103
    int great = right; // The index before the first element of right part
104

105
    if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
106
        /*
107
            * Use the second and fourth of the five sorted elements as pivots.
108
            * These values are inexpensive approximations of the first and
109
            * second terciles of the array. Note that pivot1 <= pivot2.
110
            */
111
        int pivot1 = a[e2];
112
        int pivot2 = a[e4];
113

114
        /*
115
            * The first and the last elements to be sorted are moved to the
116
            * locations formerly occupied by the pivots. When partitioning
117
            * is complete, the pivots are swapped back into their final
118
            * positions, and excluded from subsequent sorting.
119
            */
120
        a[e2] = a[left];
121
        a[e4] = a[right];
122

123
        /*
124
            * Skip elements, which are less or greater than pivot values.
125
            */
126
        while (a[++less] < pivot1);
127
        while (a[--great] > pivot2);
128

129
        /*
130
            * Partitioning:
131
            *
132
            *   left part           center part                   right part
133
            * +--------------------------------------------------------------+
134
            * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
135
            * +--------------------------------------------------------------+
136
            *               ^                          ^       ^
137
            *               |                          |       |
138
            *              less                        k     great
139
            *
140
            * Invariants:
141
            *
142
            *              all in (left, less)   < pivot1
143
            *    pivot1 <= all in [less, k)     <= pivot2
144
            *              all in (great, right) > pivot2
145
            *
146
            * Pointer k is the first index of ?-part.
147
            */
148
        outer:
149
        for (int k = less - 1; ++k <= great; ) {
150
            int ak = a[k];
151
            if (ak < pivot1) { // Move a[k] to left part
152
                a[k] = a[less];
153
                /*
154
                    * Here and below we use "a[i] = b; i++;" instead
155
                    * of "a[i++] = b;" due to performance issue.
156
                    */
157
                a[less] = ak;
158
                ++less;
159
            } else if (ak > pivot2) { // Move a[k] to right part
160
                while (a[great] > pivot2) {
161
                    if (great-- == k) {
162
                        break outer;
163
                    }
164
                }
165
                if (a[great] < pivot1) { // a[great] <= pivot2
166
                    a[k] = a[less];
167
                    a[less] = a[great];
168
                    ++less;
169
                } else { // pivot1 <= a[great] <= pivot2
170
                    a[k] = a[great];
171
                }
172
                /*
173
                    * Here and below we use "a[i] = b; i--;" instead
174
                    * of "a[i--] = b;" due to performance issue.
175
                    */
176
                a[great] = ak;
177
                --great;
178
            }
179
        }
180

181
        // Swap pivots into their final positions
182
        a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
183
        a[right] = a[great + 1]; a[great + 1] = pivot2;
184

185
        // Sort left and right parts recursively, excluding known pivots
186
        sort(a, left, less - 2, leftmost);
187
        sort(a, great + 2, right, false);
188

189
        /*
190
            * If center part is too large (comprises > 4/7 of the array),
191
            * swap internal pivot values to ends.
192
            */
193
        if (less < e1 && e5 < great) {
194
            /*
195
                * Skip elements, which are equal to pivot values.
196
                */
197
            while (a[less] == pivot1) {
198
                ++less;
199
            }
200

201
            while (a[great] == pivot2) {
202
                --great;
203
            }
204

205
            /*
206
                * Partitioning:
207
                *
208
                *   left part         center part                  right part
209
                * +----------------------------------------------------------+
210
                * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
211
                * +----------------------------------------------------------+
212
                *              ^                        ^       ^
213
                *              |                        |       |
214
                *             less                      k     great
215
                *
216
                * Invariants:
217
                *
218
                *              all in (*,  less) == pivot1
219
                *     pivot1 < all in [less,  k)  < pivot2
220
                *              all in (great, *) == pivot2
221
                *
222
                * Pointer k is the first index of ?-part.
223
                */
224
            outer:
225
            for (int k = less - 1; ++k <= great; ) {
226
                int ak = a[k];
227
                if (ak == pivot1) { // Move a[k] to left part
228
                    a[k] = a[less];
229
                    a[less] = ak;
230
                    ++less;
231
                } else if (ak == pivot2) { // Move a[k] to right part
232
                    while (a[great] == pivot2) {
233
                        if (great-- == k) {
234
                            break outer;
235
                        }
236
                    }
237
                    if (a[great] == pivot1) { // a[great] < pivot2
238
                        a[k] = a[less];
239
                        /*
240
                            * Even though a[great] equals to pivot1, the
241
                            * assignment a[less] = pivot1 may be incorrect,
242
                            * if a[great] and pivot1 are floating-point zeros
243
                            * of different signs. Therefore in float and
244
                            * double sorting methods we have to use more
245
                            * accurate assignment a[less] = a[great].
246
                            */
247
                        a[less] = pivot1;
248
                        ++less;
249
                    } else { // pivot1 < a[great] < pivot2
250
                        a[k] = a[great];
251
                    }
252
                    a[great] = ak;
253
                    --great;
254
                }
255
            }
256
        }
257

258
        // Sort center part recursively
259
        sort(a, less, great, false);
260

261
    } else { // Partitioning with one pivot
262
        /*
263
            * Use the third of the five sorted elements as pivot.
264
            * This value is inexpensive approximation of the median.
265
            */
266
        int pivot = a[e3];
267

268
        /*
269
            * Partitioning degenerates to the traditional 3-way
270
            * (or "Dutch National Flag") schema:
271
            *
272
            *   left part    center part              right part
273
            * +-------------------------------------------------+
274
            * |  < pivot  |   == pivot   |     ?    |  > pivot  |
275
            * +-------------------------------------------------+
276
            *              ^              ^        ^
277
            *              |              |        |
278
            *             less            k      great
279
            *
280
            * Invariants:
281
            *
282
            *   all in (left, less)   < pivot
283
            *   all in [less, k)     == pivot
284
            *   all in (great, right) > pivot
285
            *
286
            * Pointer k is the first index of ?-part.
287
            */
288
        for (int k = less; k <= great; ++k) {
289
            if (a[k] == pivot) {
290
                continue;
291
            }
292
            int ak = a[k];
293
            if (ak < pivot) { // Move a[k] to left part
294
                a[k] = a[less];
295
                a[less] = ak;
296
                ++less;
297
            } else { // a[k] > pivot - Move a[k] to right part
298
                while (a[great] > pivot) {
299
                    --great;
300
                }
301
                if (a[great] < pivot) { // a[great] <= pivot
302
                    a[k] = a[less];
303
                    a[less] = a[great];
304
                    ++less;
305
                } else { // a[great] == pivot
306
                    /*
307
                        * Even though a[great] equals to pivot, the
308
                        * assignment a[k] = pivot may be incorrect,
309
                        * if a[great] and pivot are floating-point
310
                        * zeros of different signs. Therefore in float
311
                        * and double sorting methods we have to use
312
                        * more accurate assignment a[k] = a[great].
313
                        */
314
                    a[k] = pivot;
315
                }
316
                a[great] = ak;
317
                --great;
318
            }
319
        }
320

321
        /*
322
            * Sort left and right parts recursively.
323
            * All elements from center part are equal
324
            * and, therefore, already sorted.
325
            */
326
        sort(a, left, less - 1, leftmost);
327
        sort(a, great + 1, right, false);
328
    }
329
}