Case Analysis of Arrays.sort () method of Java

This article mainly explains "Java Arrays.sort() method example analysis", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let Xiaobian take you to learn "Java Arrays.sort() method example analysis"!

First look at the code:

// Use Quicksort on small arraysif (right - left < QUICKSORT_THRESHOLD){ //QUICKSORT_THRESHOLD = 286 sort(a, left, right, true); return; }

As soon as the array comes in, it will encounter the first threshold QUICKSORT_THRESHOLD (286). The annotation says that the value below this threshold enters Quicksort (Quicksort). In fact, it is not all. Click in sort(a, left, right, true); Method:

// Use insertion sort on tiny arraysif (length < INSERTION_SORT_THRESHOLD){ if (leftmost) { ......

After clicking in we see the second threshold Insertion_SORT_THRESHOLD (47), if the element is less than the threshold of 47, use insertion sort, look down and it is true:

/* * Traditional (without sentinel) insertion sort, * optimized for server VM, is used in case of * the leftmost part. */for (int i = left, j = i; i < right; j = ++i){ int ai = a[i + 1]; while (ai < a[j]) { a[j + 1] = a[j]; if (j-- == left) { break; } } a[j + 1] = ai;

Elements less than 47 are sorted by insertion

For those greater than Insertion_SORT_THRESHOLD (47), use a quick sort method:

1. Five elements are selected from the sequence and are called "pivots."

2. Reorder the sequence so that all elements smaller than the reference are placed in front of the reference and all elements larger than the reference are placed behind the reference (the same number can be placed on either side). After this partition exits, the datum is in the middle of the series. This is called the partition operation;

3. Recursively sort subseries of elements smaller than the reference value and subseries of elements larger than the reference value.

Quick Sort

These are the two cases where it is less than the threshold QUICKSORT_THRESHOLD (286), and where it is greater than 286, it goes into Merge Sort, but before that, it has a little action:

// 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