“This is the fifth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”
Hi, everyone, I am three days fishing, two days drying net small 66
preface
Welcome to our GitHub repository Star: github.com/bin39232820… The best time to plant a tree was ten years ago, followed by now
Recent small brushs bit algorithm, spare time will be the reason, of course, is the too food, ha ha, is really dish, but brush some questions, find your brain don’t so silly, brush force or help thinking appears to ascend, recommend spare brush, of course, the performance of the algorithm thinking for us to write the code is helpful? Arrays.sort is a method that is often used when you swipe Arrays. Let’s see how the Java JDK does sorting
Common sorting algorithms
To understand the underlying principles of arrays.sort, let’s take a look at some of the familiar sorting algorithms. Here’s just a glimpse of these algorithms
Algorithm 1: Insertion sort
Insertion sort diagram
Insertion sort is one of the most simple and intuitive sorting algorithms. Its working principle is to build an ordered sequence and scan the unsorted data from back to front in the sorted sequence to find the corresponding position and insert it.
Algorithm steps:
1) The first element of the first to be sorted sequence is regarded as an ordered sequence, and the second element to the last element is regarded as an unsorted sequence.
2) Scan the unordered sequence from beginning to end, inserting each scanned element into the appropriate place of the ordered sequence. (If the element to be inserted is equal to an element in the ordered sequence, the element to be inserted is inserted after the equal element.)
Algorithm two: select sort
Selection sort diagram
Selection sort is also a simple and intuitive sorting algorithm.
Algorithm steps:
1) First find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence
2) Continue to find the smallest (largest) element from the remaining unsorted elements, and then put it at the end of the sorted sequence.
3) Repeat step 2 until all elements are sorted.
Algorithm three: bubble sort
Bubble sort schematic
Bubble Sort is also a simple and intuitive sorting algorithm. It repeatedly walks through the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The task of visiting an array is repeated until no more exchanges are needed, that is, the array has been sorted. The algorithm gets its name because smaller elements slowly “float” to the top of the list through swapping.
Algorithm steps:
1) Compare adjacent elements. If the first one is bigger than the second, swap them both.
2) Do the same for each pair of adjacent elements, starting from the first pair to the last pair at the end. When we do that, the last element is going to be the largest number.
3) Repeat this step for all elements except the last one.
4) Keep repeating the above steps for fewer and fewer elements at a time until there are no more pairs of numbers to compare.
Algorithm four: merge sort
Diagram of merge sort
Merge sort is an efficient sorting algorithm based on Merge operations. This algorithm is a very typical application of Divide and Conquer.
Algorithm steps:
- Apply for a space that is the sum of two sorted sequences and is used to store the combined sequence
- Sets two Pointers, starting at the start of two sorted sequences
- Compare the elements to which the two Pointers point, place the smaller element into the merge space, and move the pointer to the next position
- Repeat step 3 until a pointer reaches the end of the sequence
- Copies all remaining elements of the other sequence directly to the end of the merged sequence
Algorithm five: quicksort
Quicksort schematic
Quicksort is a sorting algorithm developed by Tony Hall. On average, n log N comparison is required to sort n two items. In the worst case, a comparison of TWO (N2) steps is required, but this is not common. In fact, quicksort is generally significantly faster than other two (N log n) algorithms because its inner loop can be implemented efficiently on most architectures.
Quicksort uses a Divide and conquer strategy to Divide one serial (list) into two sub-lists.
Algorithm steps:
1 Pick an element from the sequence, called pivot,
2 Reorder the array so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (the same number can go to either side). After the partition exits, the benchmark is in the middle of the array. This is called a partition operation.
3 Recursively sorts subsequences of elements less than the reference value and those greater than the reference value.
The bottom case of recursion is if the sequence is of size zero or one, so it’s always sorted. The algorithm always exits, though recursively, because in each iteration it puts at least one element in its last position.
Of course, there are several other sorting algorithms, we also go to understand, but we commonly used on the top 5
Arrays.sort and collections. sort
- In fact, the collections. sort method is the underlying array.sort method that is called, and either collections. sort or arrays.sort,
- Let’s keep track of the source code. First, let’s write a demo
Arrays.sort(nums1);
Arrays.sort(nums2);
int length1 = nums1.length, length2 = nums2.length;
int[] intersection = new int[Math.min(length1, length2)];
int index1 = 0, index2 = 0, index = 0;
while (index1 < length1 && index2 < length2) {
if (nums1[index1] < nums2[index2]) {
index1++;
} else if (nums1[index1] > nums2[index2]) {
index2++;
} else {
intersection[index] = nums1[index1];
index1++;
index2++;
index++;
}
}
return Arrays.copyOfRange(intersection, 0, index);
Copy the code- Click in and see
Sort the specified array in ascending numeric order. The sorting algorithm is a double-pivot quicksort designed by Vladimir Yaroslavskiy, Jon Bentley and Joshua Bloch. The algorithm provides O(n log(n)) performance over many data sets, which causes other quicksorts to degrade to quadratic performance, and is generally faster than traditional (uniaxial) quicksort implementations.
- Quicksort uses the idea of divide and conquer, which divides the original problem into several sub-problems for recursive solution. Choose an element as axis (pivot), by a trip to sort to sort data split into separate two parts, one part of all the data than the shaft element is small, another part of all the data is bigger than axial element, then according to this method to quick sort of the two parts data respectively, the entire sorting process can be recursive, So that the whole data becomes an ordered sequence.
- As the name implies, there are two axis elements, pivoT1 and pivoT2, and pivot ≤ pivoT2, to divide the sequence into three sections: X < pivot1, pivot1 ≤ x ≤ pivot2, and x >pivot2 are recursed for the three sections respectively. This algorithm is generally more efficient than traditional fast sorting, and is therefore used as a concrete implementation of sorting primitive types of data in Arrays.java.
- Moving on to our important sort method
- Check if the array length is greater than 286, merge sort is used, otherwise go to the next step
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD)
{
//QUICKSORT_THRESHOLD = 286
sort(a, left, right, true);
return;
}
Copy the code- Less than this threshold to enter Quicksort, not all, go to sort(a, left, right, true); Methods:
// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD)
{
if (leftmost)
{
......
Copy the code- When we click in, we see the second threshold, INSERTION_SORT_THRESHOLD (47). If the element is less than 47, we use insertion sort.
/*
* 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;
Copy the code- These are the two cases where the threshold is less than QUICKSORT_THRESHOLD (286). For those greater than 286, it enters the 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 <= right && a[k - 1] <= a[k]); } else if (a[k] > a[k + 1]) { // descending 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 { // equal for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) { if (--m == 0) { sort(a, left, right, true); return; } } } /* * The array is not highly structured, * use Quicksort instead of merge sort. */ if (++count == MAX_RUN_COUNT) { sort(a, left, right, true); return; }}Copy the codeconclusion
Let’s take a look at arrays.sort
O(nlogn) only represents the order of increase, and the constant in front of the same order can be different, and the actual operation time under different quantities can be different.
For very small quantities (as mentioned above, less than 47), insertion sort and so on May be faster than quicksort. So anything less than 47 goes into insert sort.
The more disordered the fast data is, the faster it will be (it will not degenerate after adding randomization), the smallest average constant, no extra space is needed, and unstable sorting.
Stable sorting speed, constant is slightly larger than fast sorting, need extra space, stable sorting.
Therefore, if the number is greater than or equal to 47 or less than 286, it is quicksorted. If the number is greater than or equal to 286, it is sorted with a minor action: “// Check if the array is nearly sorted”. The first function is to comb the data for subsequent dual-pivot merge sort. The second function is that even if the number of descending groups is greater than 286, when there are too many descending groups (judged as unstructured data, The array is not highly structured,use Quicksort instead of merge sort.), go back to Quicksort.
reference
- Sorting algorithm in detail