Arrays were observed during learning Sort (ARR) algorithm can sort directly, but I don't know what the underlying code logic looks like. I remember that I also had an interviewer ask this question in the interview question before. I can only say that after the research, it is still relatively complex, not fast sorting or two-point insertion on the Internet.
First look at the source code:
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
It calls the sort method of DualPivotQuicksort. At first glance, it seems to be a fast queue. This is what many online bloggers say. Continue to click and look down (the code is too long to be patient. You can directly skip this code QWQ):
static void sort(int[] a, int left, int right,
int[] work, int workBase, int workLen) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
/*
* Index run[i] is the start of i-th run
* (ascending or descending sequence).
*/
int[] run = new int[MAX_RUN_COUNT + 1];
int count = 0; run[0] = left;
// Check if the array is nearly sorted
for (int k = left; k < right; run[count] = k) {
if (a[k] < a[k + 1]) { // ascending
while (++k <= right && a[k - 1] <= a[k]);
} else if (a[k] > a[k + 1]) { // descending
while (++k <= right && a[k - 1] >= a[k]);
for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
}
} else { // equal
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
sort(a, left, right, true);
return;
}
}
}
/*
* The array is not highly structured,
* use Quicksort instead of merge sort.
*/
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
}
// Check special cases
// Implementation note: variable "right" is increased by 1.
if (run[count] == right++) { // The last run contains one element
run[++count] = right;
} else if (count == 1) { // The array is already sorted
return;
}
// Determine alternation base for merge
byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);
// Use or create temporary array b for merging
int[] b; // temp array; alternates with a
int ao, bo; // array offsets from 'left'
int blen = right - left; // space needed for b
if (work == null || workLen < blen || workBase + blen > work.length) {
work = new int[blen];
workBase = 0;
}
if (odd == 0) {
System.arraycopy(a, left, work, workBase, blen);
b = a;
bo = 0;
a = work;
ao = workBase - left;
} else {
b = work;
ao = 0;
bo = workBase - left;
}
// Merging
for (int last; count > 1; count = last) {
for (int k = (last = 0) + 2; k <= count; k += 2) {
int hi = run[k], mi = run[k - 1];
for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
b[i + bo] = a[p++ + ao];
} else {
b[i + bo] = a[q++ + ao];
}
}
run[++last] = hi;
}
if ((count & 1) != 0) {
for (int i = right, lo = run[count - 1]; --i >= lo;
b[i + bo] = a[i + ao]
);
run[++last] = right;
}
int[] t = a; a = b; b = t;
int o = ao; ao = bo; bo = o;
}
}
The code is very long. It is briefly translated. There are several situations:
-
Array length is less than 286
Here, a sort method will be called again, and clicking the sort() will divide the situation:
-
Array length is less than 47,
When leftmost (an imported Boolean parameter) is true, direct insertion sorting is used;
Otherwise, another insertion method will be called, and a comment can be observed here:
/* * Every element from adjoining part plays the role * of sentinel, therefore this allows us to avoid the * left range check on each iteration. Moreover, we use * the more optimized algorithm, so called pair insertion * sort, which is faster (in the context of Quicksort) * than traditional implementation of insertion sort. */
Each element of the adjacent part acts as a sentry, so this allows us to avoid checking the left range in each iteration. In addition, we use a more optimized algorithm, the so-called paired insertion sort, which is faster than the traditional implementation of insertion sort (in the context of quick sort).
Note, however, that the parameter passed to the original function parameter is true here, so it must be directly inserted and sorted. The above is for understanding.
-
The length of the array is greater than 47. A quick sorting method is adopted. Here, because the code is too long and the skill is not good, please refer to it Analysis of Bai Chunyu's article:
As for greater than INSERTION_SORT_THRESHOLD (47) uses a quick sorting method:
1. Pick out five elements from the sequence, which is called "pivot";
2. Reorder the sequence. All elements smaller than the benchmark value are placed in front of the benchmark, and all elements larger than the benchmark value are placed behind the benchmark (the same number can be on either side). After the partition exits, the benchmark is in the middle of the sequence. This is called a partition operation;
3. Recursively sort the subsequence that is less than the reference value element and the subsequence that is greater than the reference value element.
-
-
When the array length is greater than 286
At this time, go back to the long code segment. After judging the length array less than 286, from the annotation:
// Check if the array is nearly sorted
This means to check whether the array elements are about to be arranged, or to put it in writing, whether they have a certain structure, and then look at the following for loop and notice a piece of code:
if (++count == MAX_RUN_COUNT) { sort(a, left, right, true); return; }The sort method here is the same as the sort method above when the array length is less than 286. For this count, it is used to record the reverse order group, for example:
At this time, there is an array of 1 5 6 9 8 7 2 3
When the array determines that our order should be in ascending order, start from the first number. At this time, 9 8 7 2 is in descending order, which is reverse order. Synthesize these four arrays into a group called reverse order group, and then look back from 3.
When a reverse order group is counted, count + +, so it can be seen that count is used to remember the reverse order group. The more reverse order groups, the more chaotic the structure will be
MAX_RUN_COUNT == 67, so when count is continuously added to 67, it indicates that it is at a chaotic critical value. At this time, execute the sort() method
Through this analysis, let's sort out the following ideas:
If the array can run here, the length of the array is greater than or equal to 286. When this condition is met, we need to judge whether the array has a certain structure:
(1) Count < 67 indicates that it is not so chaotic and has a certain structure. Skip;
(2) Count > = 67 indicates that it is confused and has no structure. The sort method is executed. If the known array length is greater than or equal to 286, it must be greater than 47. Quick sorting must be executed.
After skipping, after a lot of pre operations of the code, I finally see a line of comments in the following code:
//Merging
Obviously, merging and sorting will be used later here, which will not be described in detail.
Well, the final conclusion:
- When the array length is less than 286, there are two cases according to the array length:
- If the array length is less than 47, use direct insertion sorting
- Array length greater than 47, use quick sort
- When the array length is greater than 286, there are two cases according to the sorting of the array:
- The order in the array is chaotic, that is, the number of count reverse groups is greater than or equal to 67. Use quick sort
- There is a certain order in the array, that is, count is in reverse order, and the number of groups is less than 67. Merge sorting is used
Welcome to the discussion
reference material:
What sort algorithm is used in Java's Arrays.sort() method https://www.cnblogs.com/baichunyu/p/11935995.html Author: Bai Chunyu
- When the array length is less than 286, there are two cases according to the array length: