On the inscription: JDK, there are many algorithm has the bright spot, it is worth to study.

**] [Java.uti.Arrays** to operate the array contains (such as sorting and searching) in various ways. This article we study a number of masters to write sorting algorithm.

**(1) sorting an array of basic data types, such as Arrays.sort (int []) and so on. After using a quick sort tuning.** The algorithm is adapted from Jon L. Bentley and M. Douglas McIlroy co-author of Engineering a Sort Function ", Software-Practice and Experience Vol. 23 (11) P. 1249-1265 (November 1993). This algorithm is in many data sets provided n * log (n) performance, which led to other quick sort would reduce the quadratic performance.

The following are in tune JDK source code for quick sort algorithm:

/** * Adds the specified range of the integer array sorted in ascending order . * x[] Pending row array * off First off from the array elements beginning sort * len The length of the array */ private static void sort1(int x[], int off, int len) { // Optimization 1: In a small (size<7) Array, directly into a sort of efficiency than quick sort high . if (len < 7) { for (int i=off; i<len+off; i++) for (int j=i; j>off && x[j-1]>x[j]; j--) swap(x, j, j-1); return; } // Optimization 2: Carefully select a Division element, i.e. the pivot // If you are a small array (size<=7), Directly from the Middle element as the pivot // If it is a medium-sized arrays (7=<size<=40), The first in the array. . Tail three locations on the number of intermediate size in a pivot // If it is a large array (size>40), The nine specified number in a pseudo-random number in the ( The number of intermediate size s) int m = off + (len >> 1); if (len > 7) { int l = off; int n = off + len - 1; if (len > 40) { int s = len/8; l = med3(x, l, l+s, l+2*s); m = med3(x, m-s, m, m+s); n = med3(x, n-2*s, n-s, n); } m = med3(x, l, m, n); } int v = x[m]; // Optimization 3: Every time the pivot of Division v , Which results in a form a shape such as (<v)* v* (>v)* An array of // Stage 1, formation v* (<v)* (>v)* v* An array of int a = off, b = a, c = off + len - 1, d = c; while(true) { while (b <= c && x[b] <= v) { if (x[b] == v) swap(x, a++, b); b++; } while (c >= b && x[c] >= v) { if (x[c] == v) swap(x, c, d--); c--; } if (b > c) break; swap(x, b++, c--); } // Phase II, will, and pivot equal exchange to the middle of the array element int s, n = off + len; s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); // Phase three, recursive sort and pivot not equal interval are elements if ((s = b-a) > 1) sort1(x, off, s); if ((s = d-c) > 1) sort1(x, n-s, s); }

★ Optimization 1: small (size <7) in the array, directly into the sort of efficiency than the high-speed sorting.

Do not have a ranking in any case are the best "summary based on the comparison of internal order." O (N ^ 2) level of the sort seems to be worse than all the more advanced sort. There are in fact not the case, Arrays of sort () algorithm gave us a good example. When the row of the array to be very small when the (JDK in the size threshold INSERTIONSORT_THRESHOLD = 7), rather than directly into the fast row sorting, merge sort is better.

The reason is simple. Array of small, relatively simple algorithm is the number of no more than the number of advanced algorithms. On the contrary, such as fast row, merge sort algorithm using recursion and other advanced operations, operating costs of higher pay.

★ Optimization 2: well-chosen partition element, that is the pivot.

Fast row has a worst-case, which degenerated into the worst start sorting efficiency (see "exchange sort"). The main causes leading to this choice is not able to pivot the entire array is divided into two roughly equal parts. For example, the basic order of the array, select the first element will be generated as the pivot of this degeneration.

That being the case, we can look Arryas.sort () is how we choose to pivot.

● If it is small-scale arrays (size <= 7), directly taking the middle element as pivot.

● If it is medium-sized array (7 = <size <= 40), the first in the array, in the end the number three position in the middle of the size of the number taken as the pivot ● If it is large-scale array (size> 40) , at 9, fetch a specified number of pseudo-median (the middle number of the size of s)

Small scale, such as to avoid borrowing from an array of smaller or larger numbers as the number of pivot. It is worth mentioning that a large scale, the first in the array to find nine data ( Can through the source code Faxian the 9 position of the data is more evenly distributed across the array only); and then every 3 months data Zhao in the median; Finally, on 3 and then find the median median as a pivot.

Think about this carefully chosen pivot, making quick arrangements for a very small probability of a worst-case incident.

★ Optimization 3: According to the pivot v divided to form a shape like (<v)* v* (> v) * array

Conventional rapid ordering scheme, is making moves to the pivot element in the array than the middle. All the elements before the pivot is less than or equal to the pivot, then all the elements greater than pivot. However, with the pivot element equal and can not be moved to a position near the pivot. This is the Arrays.sort () algorithm optimization greatly.

We give an example to illustrate the details of 15,93,15,41,6,15,22,7,15,20 Optimization Arrays

First pivot: v = 15

Stage 1, the formation of v * (<v)* (> v) * v * array:

15:15, 7,6, 41,20,22,93, 15:15

We found, with the pivot element equal on both sides to move to the array. While smaller than the pivot elements and pivot larger than the separate elements have also come.

Phase II will pivot and exchange with the pivot element equal to the middle position of the array

7,6, 15:15, 15:15, 41,20,22,93

Stage III, recursive sorting and pivot elements are not equal interval (7,6) and (41,20,22,93)

Think about it more for repeat element array, such optimization can undoubtedly get better efficiency.

**(1) sorting an array object, such as Arrays.sort (Object []) so. After using a modified merge sort.** There are also several optimized its glittering.

Here is the improved JDK source code merge sort algorithm:

/** * Adds the specified range of an array of objects according to the natural order of ascending order . * src[] The original question row of an array * dest[] Purpose to row array * low To be ranked lower bound of the array location * high To be the upper bound of an array of row position * off First off from the array elements beginning sort */ private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off) { int length = high - low; // Optimization 1: Very small array of sort, the efficiency of direct insertion sort rather than merging to high . // Scale up within the INSERTIONSORT_THRESHOLD = 7 if (length < INSERTIONSORT_THRESHOLD) { for (int i=low; i<high; i++) for (int j=i; j>low && ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--) swap(dest, j, j-1); return; } // Recursive sort dest half element and assigned to src int destLow = low; int destHigh = high; low += off; high += off; int mid = (low + high) >> 1; mergeSort(dest, src, low, mid, -off); mergeSort(dest, src, mid, high, -off); // Optimization 2: If low child list of the highest element smaller than the high child list of the minimum elements, it ignores the merge // If you need merging both ends low~(middle-1),middle~high Have been ordered, i.e. src[mid-1]==src[mid]. // Then simply copy the src low~high You can assign values to corresponding dest , There is no need to merge . if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) { System.arraycopy(src, low, dest, destLow, length); return; } // The src is a two-part merge , And assigned to dest for(int i = destLow, p = low, q = mid; i < destHigh; i++) { if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0) dest[i] = src[p++]; else dest[i] = src[q++]; } }

★ Optimization 1: Quicksort with the above

★ Optimization 2: If the low sub-list is less than the maximum element of the list of high sub-minimum element, ignore the merger. The optimization of the basic order of the sequence of measures is no doubt a great efficiency improvement.