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

- Java377 articles
- Python197 articles
- Linux110 articles
- MySQL83 articles
- Vue78 articles
- SpringBoot68 articles
- Spring61 articles
- javascript56 articles
- more...

Daily Recommendation

views 4

©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 ）