First of all, let's take a look Arrays.sort() Examples used .
Example 1:
Arrays.sort(int[] a)
// Be sure to use Integer Object class Integer[] a1 = {34, 57, 46, 89, 98, 12, 55, 84, 29};
Integer[] a2 = {34, 57, 46, 89, 98, 12, 55, 84, 29}; // Increasing order ,Arrays.sort() Default ascending
Arrays.sort(a1); System.out.println("Arrays.sort() Ascending order :"); for (int i = 0; i <
a1.length; i++) { System.out.print(a1[i] + " "); } // Descending order , available Comparator() Anonymous Inner Class
Arrays.sort(a2, new Comparator<Integer>() { @Override public int
compare(Integer o1, Integer o2) { return o2.compareTo(o1); } });
System.out.println("\nArrays.sort() Descending order :"); for (int i = 0; i < a2.length; i++) {
System.out.print(a2[i]+ " "); }
Basic knowledge points :

* If it is a basic type , Need to convert to corresponding object type ( as :int Convert to Integer)Arrays.sort() Basic object types can be sorted , But basic data types cannot be used .
* Arrays.sort() The default is ascending sort , Descending sort can adopt Collection.sort() Anonymous Inner Class .
* Array and list equally , It needs to be traversed .
The operation results are as follows :
Arrays.sort() Ascending order : 12 29 34 46 55 57 84 89 98 Arrays.sort() Descending order : 98 89 84 57 55 46
34 29 12
Example 2
Arrays.sort(int[] a, int fromIndex, int toIndex)
// Be sure to use Integer Object class Integer[] a1 = {34, 57, 46, 89, 98, 12, 55, 84, 29};
// To the fourth digit to the third in the array 7 position ( No seventh digit included )( Left closed right open principle ) Sort Arrays.sort(a1,3,6);
System.out.println("Arrays.sort() Ascending order :"); for (int i = 0; i < a1.length; i++) {
System.out.print(a1[i] + " "); }
The operation results are as follows :

Combine documentation with source code , We found that ,jdk Medium Arrays.sort() It is realized by the so-called double axis fast arrangement algorithm

Double axis quick platoon :

* Quick sort
Using the idea of divide and rule , Divide the original problem into several subproblems to solve recursively . Select an element as the axis (pivot), Divide the data to be sorted into two independent parts by one sorting , All the data in one part is smaller than the axis element , All the data in the other part is larger than the axis element , Then, the two parts of the data are sorted by this method , The whole sorting process can be carried out recursively , In order to make the whole data into an ordered sequence .
* Double axis quick platoon (DualPivotQuicksort), As the name suggests, there are two axis elements pivot1,pivot2, And pivot ≤
pivot2, Divide the sequence into three segments :x < pivot1,pivot1 ≤ x ≤ pivot2,x
>pivot2, Then recurse the three segments respectively . This algorithm is usually more efficient than the traditional fast scheduling algorithm , As a result, it was taken as Arrays.java The implementation of data sorting for basic types in .
Now let's JDK1.8 in Arrays Yes int The sorting of type a array is taken as an example to introduce the double axis fast sorting used in it :

1. Determine whether the length of the array is greater than 286, Greater than, use merge sort (merge sort), Otherwise 2.
// Use Quicksort on small arrays if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true); return; } // Merge sort ......
2. Determine whether the array length is less than 47, If it is less than, insert the order directly (insertion sort), Otherwise 3.
// Use insertion sort on tiny arrays if (length < INSERTION_SORT_THRESHOLD) {
// Insertion sort ...... }
3. Use formula length/8+length/64+1 To approximate the length of an array 1/7.
// Inexpensive approximation of length / 7 int seventh = (length >> 3) +
(length >> 6) + 1;
4. take 5 Equidistant points from experience .
/* * Sort five evenly spaced elements around (and including) the * center
element in the range. These elements will be used for * pivot selection as
described below. The choice for spacing * these elements was empirically
determined to work well on * a wide variety of inputs. */ int e3 = (left +
right) >>> 1; // The midpoint int e2 = e3 - seventh; int e1 = e2 - seventh; int
e4 = e3 + seventh; int e5 = e4 + seventh;
5. Will this 5 Elements for insertion sort
// Sort these elements using insertion sort if (a[e2] < a[e1]) { int t =
a[e2]; a[e2] = a[e1]; a[e1] = t; } if (a[e3] < a[e2]) { int t = a[e3]; a[e3] =
a[e2]; a[e2] = t; if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } } if (a[e4] <
a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t; if (t < a[e2]) { a[e3] =
a[e2]; a[e2] = t; if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } } } if (a[e5] <
a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t; if (t < a[e3]) { a[e4] =
a[e3]; a[e3] = t; if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; if (t < a[e1]) {
a[e2] = a[e1]; a[e1] = t; } } } }
6. Selection a[e2],a[e4] As pivot1,pivot2. Due to step 5 Sorted , So there must be pivot1
<=pivot2. Define two pointers less and great,less Traversal from the far left to the right , Always find the first one no less than pivot1 Elements of ,great Traverse from right to left , Always find the first one no greater than pivot2 Elements of .
/* * Use the second and fourth of the five sorted elements as pivots. * These
values are inexpensive approximations of the first and * second terciles of the
array. Note that pivot1 <= pivot2. */ int pivot1 = a[e2]; int pivot2 = a[e4];
/* * The first and the last elements to be sorted are moved to the * locations
formerly occupied by the pivots. When partitioning * is complete, the pivots
are swapped back into their final * positions, and excluded from subsequent
sorting. */ a[e2] = a[left]; a[e4] = a[right]; /* * Skip elements, which are
less or greater than pivot values. */ while (a[++less] < pivot1); while
(a[--great] > pivot2);

7. Then define the pointer k from less-1 Start traversing right to great, Less than pivot1 Element of moved to less left , greater than pivot2 Element of moved to great Right . Pay attention here , We know great Element at less than pivot2, But it's in pivot1 Size relationship of , Judgment is needed , If pivot1 Still small , Need to move to less left , Otherwise, only exchange to k place .
/* * Partitioning: * * left part center part right part *
+--------------------------------------------------------------+ * | < pivot1 |
pivot1 <= && <= pivot2 | ? | > pivot2 | *
+--------------------------------------------------------------+ * ^ ^ ^ * | |
| * less k great * * Invariants: * * all in (left, less) < pivot1 * pivot1 <=
all in [less, k) <= pivot2 * all in (great, right) > pivot2 * * Pointer k is
the first index of ?-part. */ outer: for (int k = less - 1; ++k <= great; ) {
int ak = a[k]; if (ak < pivot1) { // Move a[k] to left part a[k] = a[less]; /*
* Here and below we use "a[i] = b; i++;" instead * of "a[i++] = b;" due to
performance issue. */ a[less] = ak; ++less; } else if (ak > pivot2) { // Move
a[k] to right part while (a[great] > pivot2) { if (great-- == k) { break outer;
} } if (a[great] < pivot1) { // a[great] <= pivot2 a[k] = a[less]; a[less] =
a[great]; ++less; } else { // pivot1 <= a[great] <= pivot2 a[k] = a[great]; }
/* * Here and below we use "a[i] = b; i--;" instead * of "a[i--] = b;" due to
performance issue. */ a[great] = ak; --great; } }
8. take less-1 Element at moved to team leader ,great+1 Element at move to end of team , And put pivot1 and pivot2 Put them separately less-1 and great+1 place .
// Swap pivots into their final positions a[left] = a[less - 1]; a[less - 1] =
pivot1; a[right] = a[great + 1]; a[great + 1] = pivot2;
9. thus ,less The elements on the left are less than pivot1,great The elements on the right are greater than pivot2, Sort the two parts recursively .
// Sort left and right parts recursively, excluding known pivots sort(a, left,
less - 2, leftmost); sort(a, great + 2, right, false);

10. For the middle part , If greater than 4/7 Array length of , Probably because of the existence of repeating elements , So the less Move right to first not equal to pivot1 Where , hold great Move left to first not equal to pivot2 Where , And then less and great Recursive sorting of parts between .
/* * If center part is too large (comprises > 4/7 of the array), * swap
internal pivot values to ends. */ if (less < e1 && e5 < great) { /* * Skip
elements, which are equal to pivot values. */ while (a[less] == pivot1) {
++less; } while (a[great] == pivot2) { --great; } } ...... // Sort center part
recursively sort(a, less, great, false);
In addition, I refer to other blogs , The algorithm is as follows :
Algorithm steps
1. For very small arrays ( Length less than 47), Will use insert sort .
2. Select two points P1,P2 As axis , For example, we can use the first and last elements .
3.P1 Must compare P2 Be small , Otherwise, exchange the two elements , Now divide the array into four parts :
(1) Part I : than P1 Small elements .
(2) Part II : than P1 Big but bigger than P2 Small elements .
(3) Part III : than P2 Big elements .
(4) Part IV : Parts not yet compared .
Before starting the comparison , Except for pivot point , The rest of the elements are almost in part four , Until the end of the comparison, the fourth part has no elements .
4. Choose an element from part four a[K], Comparison with two axes , And put it in one of the first two three .
5. move L,K,G point .
6. repeat 4 5 step , Until part four, there's no element .
7. take P1 Exchange with the last element of the first part . take P2 Exchange with the first element of part three .
8. Sort the first two three parts recursively .

** summary :**Arrays.sort To an ascending array , The sorting efficiency of descending array and repeating array has been greatly improved , There are several major optimizations .
1. For small arrays , More efficient insertion sorting , Recursion to less than 47 The size of , Insert sort instead of fast sort , Significantly improved performance .
2. Two are used for double axis quick row pivot, Divide the array into 3 paragraph , Ingeniously reduces the number of recursions without significantly increasing the number of comparisons .
3.pivot Increased randomness in the choice of , But there is no random number overhead .
4. Optimized processing of duplicate data , Avoid unnecessary exchange and recursion .

Technology
©2019-2020 Toolsou All rights reserved,
Faster RCNN Explanation of series algorithm principle ( note ) Huawei certification HCIA-AI artificial intelligence Free download of documents : To introduce you to a few useful free download URL CSS architecture design MySQL An interview is a must !TP6 Application examples of verifier and correct verification data China Lunar Rover “ Moon rabbit No.2 ” A strange rock was found on the moon Programmer Tanabata Valentine's Day confession code A single key controls multiple water lamp states Jsp+Ajax+Servlet+Mysql Add, delete, modify and query ( one )