Sorting algorithm
An overview of the
The stability of
Merge sort, bubble sort, insertion sort and radix sort are stable
Selection sort, quicksort, Hill sort, heap sort are unstable
Time complexity
The four most basic algorithms: bubbling, selection, insertion, and quicksort. The time complexity of quicksort is O(n*log2n), while the other algorithms are O(n2).
| The sorting method | The average time | The worst case | stability | Additional space | note |
|---|---|---|---|---|---|
| The bubbling | O(n^2^) | O(n^2^) | stable | O(1) | N hours is better |
| choose | O(n^2^) | O(n^2^) | unstable | O(1) | N hours is better |
| Insert (easy) | O(n^2^) | O(n^2^) | stable | O(1) | Most are better sorted |
| base | O(log |
O(log |
stable | O(n) | B is the real number (0-9) and R is the cardinal number (ten hundred). |
| Hill sorting | O(nlogn) | O(n^s^) 1<s<2 | unstable | O(1) | S is the selected group |
| fast | O(nlogn) | O(n^2^) | unstable | O(nlogn) | Large n is good |
| merge | O(nlogn) | O(nlogn) | stable | O(1) | Large n is good |
| The heap | O(nlogn) | O(nlogn) | unstable | O(1) | Large n is good |
- The time complexity of common sorting algorithms cannot reach O(logN) level
- Stable and unstable refers to whether the order of two identical numbers changes before and after sorting
- Stable sorting algorithm: bubble, insert, radix, merge (tea cabinet)
- Unstable sorting algorithms are: select, Hill, fast, heap (hurry up the Hill selective heap)
Advanced sorting algorithm, the average time complexity of the four advanced sorting algorithms can reach O(nlogN)
- Hill sorting
- Quick sort
- Merge sort (stable)
- Heap sort
Quicksort, worst-case scenario, and because quicksort is essentially a commutative sort, in the worst case, the time is reduced to order N^2^.
The answer depends on the choice of the pivot. In earlier versions of quicksort, the left-most or right-most element was chosen as the pivot, and the worst would have happened:
1) The array is already sorted by same order. 2) Arrays are already sorted in reverse order. 3) All elements are the same (special case of 1, 2)
Because these cases are so common in use cases, the problem can be solved by either choosing a random pivot, or choosing the middle index of a partition as the pivot, or (especially for longer partitions) choosing the median of the first, middle, or last element of the partition as the pivot. With these changes, the worst case of quicksort is less likely, but if the largest (or smallest) element of the input array is selected as pivot, the worst case is repeated.
3. Idea of sorting algorithm:
(6) radix sort radix sort is sorted according to the low order first, then collect; And then sort it in order, and then collect it; And so on, all the way to the highest place. Sometimes some attributes are in order of precedence, first in order of low priority, then in order of high priority, the last order is the highest priority of the highest priority, the same as the low priority of the highest priority first. Radix sort is based on sorting separately, collecting separately, so it is a stable sorting algorithm.
(7) Hill sort (shell) Hill sort is the insertion sort of elements according to the asynchronous length. When the elements are disorderly at the beginning, the step size is the largest, so the number of elements in the insertion sort is very small, and the speed is very fast; When the elements are basically ordered and the step size is small, insertion sort is very efficient for ordered sequences. So, hill sort is going to take a little bit more time than O (n^2). Because of multiple insertion sorts, we know that a single insertion sort is stable and does not change the relative order of the same elements, but during different insertion sorts, the same elements may move in their respective insertion sorts and eventually their stability will be disturbed, so shell sorts are unstable.
We know that the structure of the heap is that the children of node I are 2i and 2i+1 nodes. The big top heap requires that the parent node be greater than or equal to its 2 children, and the small top heap requires that the parent node be less than or equal to its 2 children. In a sequence of length n, the process of heap sorting starts from the n/2 value and its children choose the largest (big top heap) or the smallest (small top heap). The choice between these three elements will not destroy the stability of course. But when n/2-1, n/2-2… 1 When these parent nodes select elements, they break stability. It is possible that the NTH / 2nd parent swaps the last element, but the NTH /2-1 parent does not swap the last identical element, and the stability between the two identical elements is broken. So heap sort is not a stable sort algorithm
Application scenarios of sorting algorithms
Less data
Insertion sort
Basically ordered data
Insertion sort
Huge amounts of data
Heap sort
The first n numbers
Heap sort
Large space and sufficient resources require time efficiency
Merge sort
Don’t know what to use
Quick sort
In terms of average time performance, quicksort is the best, requiring the least amount of time, but in the worst case, quicksort is inferior to heap sort and merge sort.
When the space is large and the resources are sufficient, and time efficiency is required, merge sort can be used.
Massive data heap sort
Heap sort, though slower than fast sort, is particularly suitable for sorting massive data. Find the top 1000 data points out of a million data points. You can build a small top heap to store 1000 elements.
When the records in the sequence are basically ordered or the n value is small, insertion sort is the best sorting method.
Radix sort works best for sequences with large cardinals but small keywords.
Bubble sort
The basic idea of bubble sort
Is the comparison and exchange between adjacent elements, double cycle O(n2); So, if two adjacent elements are equal, they don’t swap. So it’s a stable way of sorting
Time complexity of bubble sort
O(n^2^)
Is bubble sort stable
is
Application scenario of bubble sort
Bubble sort code
public class BubbleSort08 {
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = true;
for (int j = 0; j < arr.length - 1; j++) {
if(arr[j] > arr[j+1]) {int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = false; }}if(flag){
break; }}}public static void main(String[] args) {
int[] arr = new int[] {11.8.9.1.22, -5.3};
System.out.println("Before sorting:"+ Arrays.toString(arr));
bubbleSort(arr);
System.out.println("After sorting:"+Arrays.toString(arr)); }}Copy the codeSelection sort
The idea of selection sorting
Each element is compared to the first, resulting in a double cycle O(n^2^); For example, 5, 8, 5, 2, 9, after the first pass, the 2 will swap with the 5, so the order of the two 5’s in the original sequence will be broken. So it’s not a stable sorting algorithm
Select the time complexity of the sort
O(n^2^)
Is the selection sort stable
It isn’t.
For example: arr = {5, 8, 5, 2, 9} After the first sorting arr = {2, 8, 5, 5, 9} the order of the two 5’s in the original sequence changes, so it is not a stable sorting algorithm
Select the application scenario for sorting
public class SelectSort10 {
public static void selectSort(int[] arr){
for(int i = 0; i < arr.length-1; i++){int min = arr[i];
int minIndex = i;
boolean flag = false;
for(int j = i + 1; j < arr.length; j++){if(arr[j] < min){
minIndex = j;
min = arr[j];
flag = true; }}if(flag){ arr[minIndex] = arr[i]; arr[i] = min; }}}public static void main(String[] args){
int[] arr = new int[] {3.3.34.6, -1.2.65};
System.out.println("Before sorting:"+ Arrays.toString(arr));
selectSort(arr);
System.out.println("After sorting:"+ Arrays.toString(arr)); }}Copy the codeInsertion sort
Insert the idea of sorting
The basic idea of insertion sort is to treat the n elements to be sorted as an ordered table and an unordered table. At the beginning, the ordered table contains only a number of elements, and the unordered table contains n-1 elements. Every time the process of sorting table to retrieve the first element from the chaos, he and orderly table the last element of comparison, * * (1) if bigger than he is directly inserted in the back, if; (2) Otherwise, go straight ahead to find where it should be inserted; (3) If an equal element is encountered, place the element after the equal element. ** So the order of elements does not change, that is, the algorithm is stable.
Disadvantages: When the number to be inserted is a small number, the number of moves after the number is significantly increased
Time complexity of insert sort
O(n^2^)
Is insertion sort stable
Yes, ** (1) if it is bigger than he directly inserted in the back, if; (2) Otherwise, go straight ahead to find where it should be inserted; (3) If an equal element is encountered, place the element after the equal element. ** So the order of elements does not change, that is, the algorithm is stable
Application scenarios of insert sort
(1) Small amount of data
(2) The data is basically orderly
Insert sort example
Insert sort code
public static void insertSort(int[] arr) {
// An n-digit array is sorted n-1 times
for (int i = 0; i < arr.length - 1; i++) {
// Store insertVal to prevent subsequent loss
int insertVal = arr[i+1];
// insertIndex without I, because I is an important variable, you can't add or subtract I directly
//insertIndex refers to the index of the first digit of an unordered table
int insertIndex = i;
// Compare the first digit of the unordered table to the ordered table, if the first digit of the unordered table is less than the ordered table
// Assigns the value of the preceding index number to the following number
//index--
// To facilitate the comparison of numbers in the next ordered table
while(insertIndex >= 0 && insertVal < arr[insertIndex]){
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
arr[insertIndex + 1] = insertVal; }}Copy the codeRadix sort
The idea of radix sort
Radix sort is sorted by low order and then collected; And then sort it in order, and then collect it; And so on until you get to the highest place. Radix sort is a stable sorting algorithm based on sorting separately and collecting separately
Time complexity of radix sort
Base O(log R B) O(log R B) stable O(n) B is true (0-9), R is the base (ten hundred)
Overview of radix Sort
Radix sort belongs to “distribution sort”
Radix sort is stable sort
Radix sort is a classic time-for-space method, which takes up a lot of memory and is prone to cause OutofMemoryErrors when sorting massive data
The process of sorting radix
The first round of sorting: (1) take out the units digit of each element, and then see which bucket the number should be placed in (2) in the order of the bucket (according to the index of the array, put the data in the original array)
The second round of sorting: (1) take out the ten digits of each element, and then see which bucket the number should be placed in (2) according to the order of the bucket (according to the index of the array, put the data in the original array)
The third round of sorting: (1) take out the hundreds of each element, and then see which bucket the number should be placed in (2) according to the order of the bucket (according to the index of the array, put the data in the original array)
Merge sort
The basic idea of merge sort
Merge sort is to recursively divide an array into a short array, which is a recursive exit if the following conditions are met: the short array has only one element (considered directly ordered). Then merge the ordered arrays into a long ordered array, and keep merging until the original arrays are sorted.
Time complexity of merge sort
O(nlogn)
Is merge sort stable
Is. You can see that when you have one or two elements, one element doesn’t swap. If two elements are equal in size, they don’t swap, and that doesn’t break the stability.
Hill sorting
Hill’s idea of ordering
Hill sort is the insertion sort of elements according to the asynchronous length. When the elements are disorderly at the beginning, the step size is the largest, so the number of elements in insertion sort is very small, and the speed is very fast. When the elements are basically ordered and the step size is small, insertion sort is very efficient for ordered sequences. Because of multiple insertion sorts, we know that a single insertion sort is stable and does not change the relative order of the same elements, but during different insertion sorts, the same elements may move in their respective insertion sorts and eventually their stability will be disturbed, so shell sorts are unstable
Time complexity of Hill sort
Average: O(nlogn) worst O(n^s^) 1<s<2
Is hill’s order stable
It isn’t. Because of multiple insertion sorts, we know that a single insertion sort is stable and does not change the relative order of the same elements, but during different insertion sorts, the same elements may move in their respective insertion sorts and eventually their stability will be disturbed, so shell sorts are unstable
Heap sort
An overview of heap sorting
- Heap sort is a kind of sorting algorithm designed by using heap data structure. Heap sort is a kind of selection sort, whose worst, best and average time complexity are O(Nlogn) (also known as: linear logarithmic order), and it is also unstable sort
The nature of the heap
- The heap is a complete binary tree
- The heap has the following properties :(1) the value of each parent node is greater than the value of its left and right children; (2) The heap does not require a value size relationship between left and right child nodes, which is inconsistent with binary search tree/sorting tree/AVL tree/red-black tree
- Big top heap: Each parent has a value greater than the left and right children
- Small top heap: Each parent has a value less than the left and right children
- The last non-leaf node is numbered N / 2-1
extension
Heapsort (complete binary tree) the reason why the ordinal number of the last non-leaf node is N /2-1
Heap sort is implemented based on full binary tree. When adjusting an array into a heap, one of the keys is to determine the number of the last non-leaf node, which is n/2-1. N is the length of the array. But why?
Two scenarios can be considered:
① If the last non-leaf node in the heap is only the left child
② The last non-leaf node of the heap has about two children
One of the properties of a complete binary tree is that if the node is numbered I, its left child is numbered 2i+1 and its right child is numbered 2i+2.
(1) The serial number of the left child is N-1, then n-1=2* I +1, deduce I =n/2-1;
For the child whose serial number is n-2, when n-2=2i+1, it follows that I =(n-1)/2-1; If the serial number of the child on the right is N-1, then n-1=2i+2, then I =(n-1)/2-1;
Obviously, a complete binary tree has an even number of nodes when the last node is the left child of its parent. A complete binary tree has an odd number of nodes when the last node is the right child of its parent.
If n is odd, (n-1)/2-1=n/2-1. If n is odd, (n-1)/2-1=n/2-1.
Therefore, the serial number of the last non-leaf node of ② is also N /2-1.
Have to pass.
Obviously the serial number starts at zero.
Source: www.cnblogs.com/malw/p/1054…
At the same time, we numbered the nodes in the heap by layer, and mapped this logical structure into an array like this
The array is logically a heap structure. Let’s use a simple formula to describe the definition of a heap:
Arr [I] >= ARr [2i+1] &&arr [I] >= ARr [2I +2]
Small top heap: ARr [I] <= ARr [2i+1] &&arr [I] <= arr[2i+2]
The basic idea of heap sort is to construct the sequence to be sorted as a big top heap, in which the maximum value of the whole sequence is the root node of the top of the heap. Swap it with the trailing element, where the trailing element is the maximum. The remaining n-1 elements are then reconstructed into a heap, which yields the subsmallest values of n elements. Do this repeatedly, and you get an ordered sequence
The basic idea of heap sort
- The sequence to be sorted is constructed into a large top heap
- At this point, the maximum value of the entire sequence is the root node at the top of the heap
- Swap it with the trailing element, where the trailing element is the maximum
- Then you reconstruct the remaining n minus 1 elements into a heap, so you get a small number of n elements, and you do that over and over again, and you get an ordered sequence
Heap sort example
Step one constructs the initial heap. The given unordered sequence is constructed into a big top heap (generally the big top heap is used for ascending order and the small top heap is used for descending order).
A. Assume the given unordered sequence structure is as follows
2. At this time, we start from the last non-leaf node (leaf node naturally need not be adjusted, the first non-leaf node arr. Length /2-1=5/2-1=1, namely the following 6 nodes), from left to right, from bottom to top.
4. Find the second non-leaf node 4, since the element 9 in [4,9,8] is the largest, 4 and 9 are swapped.
At this time, swapping leads to structural disorder of the child roots [4,5,6], further adjustment,6 is the largest in [4,5,6], and swapping 4 and 6.
At this point, we construct a large top heap from an unnecessary sequence.
Step two swaps the top element with the end element to maximize the end element. We then continue to adjust the heap, swapping the top element with the bottom element to get the second largest element. And so on and so forth.
A. Swap the top element 9 with the bottom element 4
B. Readjust the structure so that it continues to meet the heap definition
C. Then swap the top element 8 with the bottom element 5 to get the second largest element 8.
The follow-up process, continue to adjust, exchange, so repeated, eventually making the sequence order
Code implementation
public class HeapSort00 {
public static void main(String[] args) {
// Ascending order: big top heap; Descending order. Small cap pile
int[] arr = {4.6.8.5.9};
heapSort(arr);
}
// Write a heap sort method
public static void heapSort(int[] arr) {
int temp = 0;
System.out.println("Heap sort!!");
// Adjust the structure from bottom to top and from right to left from the first non-leaf node
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
// Adjust the heap structure + swap the top and bottom elements until the whole heap is in order
for (int j = arr.length - 1; j > 0; j--) {
// Swap the top element with the end element
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
// Resize the heap
adjustHeap(arr, 0, j);
}
System.out.println("Array:" + Arrays.toString(arr));
}
/** * function: the tree corresponding to the non-child node of I is adjusted to the big top heap **@paramArr Array to be adjusted *@paramI The index of the non-leaf node in the array *@paramLength indicates how many elements are being adjusted, and length is gradually decreasing */
public static void adjustHeap(int[] arr, int i, int length) {
// The value of a non-leaf node
int temp = arr[i];
// Start adjusting
/** * initial value: int k = I * 2 + 1 indicates the index of the left child of the node whose index is I * step size: k = k * 2 + 1 indicates the left child of the node whose index is I */
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
// Compare the left child with the right child
//arr[k] < arr[k+1] Indicates that the value of the left child is smaller than that of the right child
If (k+1
if (k + 1 < length && arr[k] < arr[k + 1]) {
k++;//k points to the right child node
}
// Compare the value of the right child with the parent
if (arr[k] > temp) {// If the child is larger than the parent
arr[i] = arr[k];// Assign the value of the larger child to the current node
i = k;// set I to k to continue the loop comparison
} else {
// If the value of the parent node is already greater than the value of the child node, it ends
break; }}// When the for loop ends, we have placed the maximum value of the tree with I at the top (the top of the child tree)
arr[i] = temp;// Put temp in the adjusted position}}Copy the codeconclusion
- The unordered sequence is constructed into a heap, and the large or small top heap is constructed according to the ascending or descending requirements
- Swap the top element with the end element, “sinking” the largest element to the end of the array
- Rearrange the structure so that it meets the definition of the heap, and then continue swapping the top element with the current end element, repeating the adjust + swap step until the sequence is in order
Usage scenarios
== Priority queues usually implement == using heap sort
Quick sort
Blog.csdn.net/sinat_20177…
The idea of quicksort
Pick a random number (usually the first number) and insert it in such a way that the number to its left is smaller than it and the number to its right is larger than it. This splits an array into two subarrays, and then splits the subarrays into smaller subarrays in the same way until it can’t be split
The sample array
a[10] = {6.1.2.7.9.3.4.5.10.8}
Copy the codeReference value: A [0] = 6
Perform the steps: Place the number less than 6 in the array to the left of 6, and the number greater than 6 to the right
Set two sentinels I and j on the array, I pointing to the first element, a[0], and j to the last element, a[10]
First, the sentry J sets out. In the process, if he finds a number larger than 6, he keeps moving (j–) until he finds a number less than 6 and stops
Next, sentry I starts out, and as it moves, if it finds an array smaller than 6, it keeps moving (I ++) until it finds a number greater than 6 and stops
After this cycle, sentry I and J stop at position 7 and 5 respectively
So we want to swap 5, which is less than 6, with 7, which is more than 6
Figure after exchange
At this point, the first exchange ends, but since sentry I and Sentry J have not yet met, the operation is repeated
As is shown in
After the second swap, sentry I and Sentry J still don’t meet.
Next, Sentry J continues with (j–) and finds that 3 is less than 6, so sentry J stays above 3
Then I continues to move to the right (I ++), and now I ==j, and the iteration is complete, and the iteration is finished
The value of a[I] is then swapped with the value of the base (the first position in the array)
So the array becomes an array bounded by 6, smaller to the left of 6, larger to the right of 6
