Sorting algorithm of array (JDK1.8)
array
Arrays differ from other containers in three ways : efficiency , Types and the ability to keep basic types . stay Java in , Array is the most efficient way to store and access the sequence of object references randomly . An array is a simple linear sequence . The advantage of arrays is that access to elements can be very fast , But the cost is that once the size of the container is determined , It can't be changed . It may be suggested ArrayList, Because it can create a new instance and pass the old one in , So as to achieve expansion . Just like my last article about StringBuilder The data structure is the same , But we need to know that the underlying layer of them is array based . So List We'll talk about arrays before .
No matter what type of array to use , The array identifier is just a reference , Points to a real object created in the heap . This object is used to hold references to other objects . You can implicitly create this object as part of array initialization syntax , Or use new Explicit creation of expressions . Whether it is an array of basic data type or array of reference data type, it is basically the same in use
stay C/C++ in , You cannot return an array , Only pointers to arrays can be returned , But this can make the life cycle of the array difficult . It is easy to cause memory leak . And in the Java But it can return an array directly . It exists when it is needed , The garbage processor cleans it up when it's not needed
Arrays
Arrays Is a tool class used to manipulate arrays . Because we use arrays , It is often necessary to make changes to the elements inside . In order to save the programmer to repeat the algorithm , therefore Java The tool class has been provided . stay Arrays Methods in a class are basically static , So we don't need to go new An object .
sort method
byte Type array
Arrays.sort Method can implement different sort according to the size and type of the array . When the array type is byte Array with length less than 29 When , Insert sort is used
for (int i = left, j = i; i < right; j = ++i) { byte ai = a[i + 1]; while (ai <
a[j]) { a[j + 1] = a[j]; if (j-- == left) { break; } } a[j + 1] = ai; }
greater than 29 Count sorting is used
int[] count = new int[NUM_BYTE_VALUES]; for (int i = left - 1; ++i <= right;
count[a[i] - Byte.MIN_VALUE]++ ); for (int i = NUM_BYTE_VALUES, k = right + 1; k
> left; ) { while (count[--i] == 0); byte value = (byte) (i + Byte.MIN_VALUE);
int s = count[i]; do { a[--k] = value; } while (--s > 0); }
int Type array
When the array type is int When , If the length of the array is less than 47 Insert sort is used
if (leftmost) { 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; }
If greater than 47 less than 286, Quick sort is used
do { if (left >= right) { return; } } while (a[++left] >= a[left - 1]); for (
int k = left; ++left <= right; k = ++left) { int a1 = a[k], a2 = a[left]; if (a1
< a2) { a2 = a1; a1 = a[left]; } while (a1 < a[--k]) { a[k + 2] = a[k]; } a[++k
+ 1] = a1; while (a2 < a[--k]) { a[k + 1] = a[k]; } a[k + 1] = a2; } int last =
a[right]; while (last < a[--right]) { a[right + 1] = a[right]; } a[right + 1] =
last; }
When the length is greater than 286 Merge sort will be used
int[] run = new int[MAX_RUN_COUNT + 1]; int count = 0; run[0] = left; for (int
k= left; k < right; run[count] = k) { if (a[k] < a[k + 1]) { while (++k <= right
&& a[k - 1] <= a[k]); } else if (a[k] > a[k + 1]) { 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 { for (int m = MAX_RUN_LENGTH; ++k <=
right&& a[k - 1] == a[k]; ) { if (--m == 0) { sort(a, left, right, true); return
; } } }
float Type array
When the array is float It's more complicated when it comes to type A . Because it will be divided into different stages to operate
The first stage
Will not be float The element of is moved to the end ,isNaN Method here is to determine whether an element is a float
while (left <= right && Float.isNaN(a[right])) { --right; } for (int k = right;
--k >= left; ) { float ak = a[k]; if (ak != ak) { a[k] = a[right]; a[right] = ak
; --right; } } public static boolean isNaN(float v) { return (v != v); }
The second stage
As long as it is float The elements of are sorted according to the rules
private static void doSort(float[] a, int left, int right, float[] work, int
workBase, int workLen) { if (right - left < QUICKSORT_THRESHOLD) { sort(a, left,
right, true); return; } int[] run = new int[MAX_RUN_COUNT + 1]; int count = 0;
run[0] = left; for (int k = left; k < right; run[count] = k) { if (a[k] < a[k +
1]) { while (++k <= right && a[k - 1] <= a[k]); } else if (a[k] > a[k + 1]) {
while (++k <= right && a[k - 1] >= a[k]); for (int lo = run[count] - 1, hi = k;
++lo < --hi; ) { float t = a[lo]; a[lo] = a[hi]; a[hi] = t; } } else { for (int
m= MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) { if (--m == 0) { sort(a,
left, right, true); return; } } } if (++count == MAX_RUN_COUNT) { sort(a, left,
right, true); return; } } if (run[count] == right++) { run[++count] = right; }
else if (count == 1) { return; } byte odd = 0; for (int n = 1; (n <<= 1) < count
; odd ^= 1); float[] b; int ao, bo; int blen = right - left; if (work == null ||
workLen< blen || workBase + blen > work.length) { work = new float[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; } 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; } float[] t = a; a = b;
b= t; int o = ao; ao = bo; bo = o; } }
When the length is less than 47 It is insert sort
if (length < INSERTION_SORT_THRESHOLD) { if (leftmost) { 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; } } else { do { if (left >= right
) { return; } } while (a[++left] >= a[left - 1]); for (int k = left; ++left <=
right; k = ++left) { int a1 = a[k], a2 = a[left]; if (a1 < a2) { a2 = a1; a1 = a
[left]; } while (a1 < a[--k]) { a[k + 2] = a[k]; } a[++k + 1] = a1; while (a2 <
a[--k]) { a[k + 1] = a[k]; } a[k + 1] = a2; } int last = a[right]; while (last <
a[--right]) { a[right + 1] = a[right]; } a[right + 1] = last; } return; }
stage 3: Final order
int hi = right; while (left < hi) { int middle = (left + hi) >>> 1; float
middleValue= a[middle]; if (middleValue < 0.0f) { left = middle + 1; } else { hi
= middle; } } while (left <= right && Float.floatToRawIntBits(a[left]) < 0) { ++
left; } for (int k = left, p = left - 1; ++k <= right; ) { float ak = a[k]; if (
ak!= 0.0f) { break; } if (Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f a[k]
= 0.0f; a[++p] = -0.0f; } }
double Type array
and float be the same in essentials while differing in minor points , It's omitted here ~
String Type array
Due to the Java in String Is a class, not a keyword , So at the bottom, it becomes Object Sorting of type arrays
public static void sort(Object[] a) { if (LegacyMergeSort.userRequested)
legacyMergeSort(a); else ComparableTimSort.sort(a, 0, a.length, null, 0, 0); }
The sort here will be used ComparableTimSort class , about ComparableTimSort Class introduction translation is like this : This is {@link
TimSort} An approximate copy of , After modification, it can be implemented with {@link
Comparable} Object array of , Instead of using an explicit comparator . If you are using optimize virtual machine , You may find that TimSort And return only {@code（（Comparable）first）.compareTo（Second）} Comparator of . If this is the case , It is best to remove comparable time sorting to eliminate code duplication .
static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int
workLen) { assert a != null && lo >= 0 && lo <= hi && hi <= a.length; int
nRemaining= hi - lo; if (nRemaining < 2) return; if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi); binarySort(a, lo, hi, lo +
initRunLen); return; } ComparableTimSort ts = new ComparableTimSort(a, work,
workBase, workLen); int minRun = minRunLength(nRemaining); do { int runLen =
countRunAndMakeAscending(a, lo, hi); if (runLen < minRun) { int force =
nRemaining<= minRun ? nRemaining : minRun; binarySort(a, lo, lo + force, lo +
runLen); runLen = force; } ts.pushRun(lo, runLen); ts.mergeCollapse(); lo +=
runLen; nRemaining -= runLen; } while (nRemaining != 0); assert lo == hi; ts.
mergeForceCollapse(); assert ts.stackSize == 1; }
char Type array
When char Type array length less than 3200 Call the dosort method , and float The second stage of sequencing is very similar
private static void doSort(char[] a, int left, int right, char[] work, int
workBase, int workLen) { if (right - left < QUICKSORT_THRESHOLD) { sort(a, left,
right, true); return; } int[] run = new int[MAX_RUN_COUNT + 1]; int count = 0;
run[0] = left; for (int k = left; k < right; run[count] = k) { if (a[k] < a[k +
1]) { while (++k <= right && a[k - 1] <= a[k]); } else if (a[k] > a[k + 1]) {
while (++k <= right && a[k - 1] >= a[k]); for (int lo = run[count] - 1, hi = k;
++lo < --hi; ) { char t = a[lo]; a[lo] = a[hi]; a[hi] = t; } } else { for (int m
= MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) { if (--m == 0) { sort(a,
left, right, true); return; } } } if (++count == MAX_RUN_COUNT) { sort(a, left,
right, true); return; } }
When the length is greater than 3200 Count sort will be used
if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) { int[] count =
new int[NUM_CHAR_VALUES]; for (int i = left - 1; ++i <= right; count[a[i]]++ );
for (int i = NUM_CHAR_VALUES, k = right + 1; k > left; ) { while (count[--i] ==
0); char value = (char) i; int s = count[i]; do { a[--k] = value; } while (--s >
0); } }
Technology