- Sort of sort
- Time frequency and characteristics
- Time complexity
- Bubble sort
- Selection sort
- Insertion sort
- Hill sorting
- Quick sort
- Merge sort
- Radix sort
- Heap sort
The following ideas and key methods are only given. The source code of the algorithm is put in Git, and you need to take it yourself
leidl97/algorithm-src
Sort of sort
Sort is divided into internal sort and external sort
It is generally an internal sort, which can be divided into 8 sorts
Insertion sort: direct insert | hill sorting
Simple selection sort: choose | heap sort
Exchange sort, bubble sort | quick sort
Merge sort (divide-and-conquer)
Radix sort (bucket sort)
Time frequency and characteristics
1. The constant term can be ignored
2. The low power term can be ignored
3. The coefficient of the power term is negligible
Time complexity
1. In general, the number of repeated execution of basic operation statements in the algorithm is a function of problem size N, expressed by T(n). If there is some auxiliary function F (n), such that when n approaches infinity, the limit value of T(n)/f(n) is a constant not equal to 0, then F (n) is said to be a function of the same order of magnitude as T(n). Written as T(n) = O(f(n)), O(f(n)) is called the asymptotic time complexity of the algorithm, or time complexity for short
2. T(n) is different, but the time complexity may be the same
Calculation method
The constant 1 is used to represent all addition constants in operation
Only the highest order terms are kept
Get rid of the highest-order coefficients
Commonly used time complexity
From small to large
Constant order O(1) : no complex structure such as cycle
Log order O(log2n) : if (I < n) keep iterating I = I * 2, n is large enough to execute log2n times, that is, 2^ times =n, times =log2n
Linear order O(n) : i++ or a layer of for loop, which means the same thing, as many times as n
Linear logarithmic order O(nlog2n) : There is a logarithmic order in the for loop
Square order O(n^2) : two-level for loop
Cubic order O(n^3) : three-level for loop
KTH order O(n^k) : n-layer for loop
Order O(2^n) :
Images from the Internet
Bubble sort
Idea: Two for loops, comparing the array size -1 times, comparing the array size -1 times, starting with the first number in the array and comparing it to the next one, swapping if the first number is larger than the second, or comparing the second to the third
Code implementation
Public static void sort(int[] a) {Boolean flag = true; public static void sort(int[] a) { for (int i = 0; i < a.length - 1; I++) {// sort n-1 for (int j = 0; j < a.length - 1 - i; j++) { if (a[j] > a[j+1]) { swag(a,j,j+1); flag = false; } } if (flag) { break; } else {// do not reset as long as the exchange of useless flag = true; }}}Copy the code
Selection sort
thought
Iterate through the array, compare the first one, and see if the second one is smaller than this one. If so, swap. If not, compare the second one, and compare the array size -1 times
Code implementation
private static void sort(int[] a) { for (int i = 0; i < a.length-1; i++) { for (int j = i; j < a.length-1; J++) {if (a < [m + 1] a [I]) {/ / exchange two Numbers swag (a, I, j + 1); }}}}Copy the code
Insertion sort
Idea: Think of the data in an array as two arrays, ordered and unordered. Since the first one does not need to be compared, it needs to be compared n-1 times. Compare the first one that does not need to be compared with the last one that does not need to be compared, and insert it in the appropriate position
One for loop, one while solution
Start with the second element of the array, compare with the previous one successively, if it is small, compare until it encounters a large one, then move the found element back, insert the compared element after the found element, end of one round, total need array size -1 round of comparison
Images from the Internet
Code implementation
private static void sort(int[] a) { for (int i = 0; i < a.length-1; i++) { int arr = a[i+1]; int index = i; while (index >= 0 && arr < a[index]) { a[index + 1] = a[index]; index--; } a[index+1] = arr; }}Copy the code
Hill sorting
If there is an array {2,3,4,5,6,1} then the algorithm is slow to use insertion sort
So it’s an optimization of insertion sort, which is sort by group, also known as reduced incremental sort
Images from the Internet
Why is Hill sorting more efficient
At the beginning, the step size is large, and there are fewer elements in each sub-sequence, so the sorting speed is fast. At the end of sorting, the step size becomes smaller and the number of elements in the sub-sequence increases gradually. However, due to the previous work, most elements have been basically ordered, so the sorting speed is still fast. You know, you make more judgments, you move less, so you go faster.
Code implementation
private static void shellSort(int[] a) { int count = 0; for (int gap = a.length /2; gap > 0; gap /= 2) { for (int i = gap; i < a.length; i++) { int index = i; int arr = a[index]; if (arr < a[index-gap]) { while (index - gap >= 0 && arr < a[index-gap]) { count ++ ; a[index] = a[index-gap]; index-=gap; } a[index] = arr; }} system.out.println (" total: "+count+"); } int[] a = {4,3,5,2,1,9,8,10,7,6};Copy the code
The same array takes 16 insertions and only 8 with hill
Quick sort
Feature is recursive, through a median, the number of sides of good sorting, first find a benchmark, generally for the array size / 2, on the left to find a number larger than benchmark, the right to find a number of smaller than benchmark, then exchanged, calculate the left after all is smaller than at baseline, right side is larger than the benchmark, but cannot guarantee that they are ordered, So you also need to do a second sort on the left and right generated data
Code implementation
private static void sort(int left, int right, int[] arr) { int l = left; int r = right; int center = arr[(l+r)/2]; int temp = 0; while (l < r) { while (arr[l] < center) { l += 1; } while (arr[r] > center) { r -= 1; } if (l >= r) { break; } temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; l+=1; r-=1; } if (l == r) { l+=1; r-=1; } if (left < r) { sort(left,r,arr); } if (right > l) { sort(l,right,arr); }}}Copy the code
Merge sort
Merge sort is stable sort, it is also a very efficient sort, can take advantage of the full binary tree characteristics of sorting generally not too bad performance. Arrays.sort() in Java uses a sort algorithm called TimSort, which is an optimized version of merge sort. Every time you can see from the above figure, merge the average time complexity is O (n), and the depth of full binary tree is | log2n |. The total average time complexity is O(nlogn). In addition, merge sort is best, worst, the average time complexity is O(nlogn).
Divide and conquer
Image source network
Image source network
thought
First, divide a group of data in the array, and finally compare the divided data and then compare and merge them step by step
Code implementation
private static void sort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; // sort(arr, left, mid); // sort(arr, mid + 1, right); // Merge merge(arR, left, mid, right); } } private static void merge(int[] arr, int left, int mid, int right) { count ++ ; int i = left; int j = mid + 1; int[] temp = new int[right-left+1]; int t = 0; While (I < = mid & j < = {right) if (arr [I] < arr [j]) {/ / to the left, to the left of the number to be included in the array \ [t++] = arr [i++]; }else {temp[t++] = arr[j++];}else {temp[t++] = arr[j++]; }} / / the rest of the data to be included in the array while (I < = mid) {\ [t++] = arr [i++]; } while (j <= right) { temp[t++] = arr[j++]; } // Put temp data into arR t = 0; while (t < temp.length) { arr[left++] = temp[t++]; }}}Copy the code
Radix sort
Images from the Internet
The difficulties in
1. Take the largest number of digits in the array
2, take the power
3, to find the traversal should take the one bit or what bit, how to take
4. How should buckets be created
Code implementation
private static void sort(int[] arr) { int max = arr[0]; for (int i = 0; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } int size = (max + "").length(); /** * size = 1; /** * size = 1; /** * size = 1; /** * size = 1; /** * size = 1; /** * size = 1; */ for (int k = 0, n = 1; k < size; K++, n *= 10) {int[][] bucket = new int[arr.length][10]; for (int i = 0; i < arr.length; i++) { int temp = arr[i]; int gewei = temp / n % 10; bucket[i][gewei] = temp; } int t = 0; for (int i = 0; i < 10; i++){ for (int j = 0; j < arr.length; j++){ if (bucket[j][i] ! = 0) { arr[t++] = bucket[j][i]; } } } System.out.println(Arrays.toString(arr)); }}Copy the code
Heap sort (sort using the idea of sequential storage binary trees)
Relevant concepts
Heap this kind of data structure is a sort algorithm, heap sort is a kind of choice sort, its worst best, average complexity is not Nlogn, for unstable sort
Big top heap: Each node has a value greater than or equal to the value of its left and right children, as shown below
Small top heap: In contrast, each node has a value less than or equal to the value of its left and right children, as shown below
The size is for vertices, usually in ascending order for the big top heap and descending order for the small top heap
Heapsort idea
If it is in ascending order, that is, from small to large, then you need to build the big top heap and swap the root node element with the last leaf, repeating the process except for the already filtered leaf nodes
Or you could sort an array like a tree. A tree is just a logical concept
The steps are shown below at the beginning
1. First find the first non-leaf node, formula A. Length / 2-1, and exchange the large value of leaf node
2. Repeat the operation 1 after finding the next non-leaf node
3. Sort the left subtree before returning, because the structure is already in disorder (the program does not need recursion how to return, in the previous step has done traversal operation, can be considered as 23 together)
4. Finally form a big top heap, swap the top element with the last leaf node, remove the value, and continue the process above
5. Re-structure and continue to build the Big top heap
6. Repeat
The difficulties in
1. Build the big top heap/build the small top heap
2. Boundary value judgment
The code written by myself is as follows. After thinking about this complexity, how can n2
Public class HeapSort {public static void main(String[] args) {int[] a = {4,6,8,5,9}; System.out.println(" array :"+ array.toString (a)); sort(a); System.out.println(" array after :"+ array.toString (a)); } private static void heapSort(int[]) private static void heapSort(int[]) private static void heapSort(int[]) A, int I, int length) {a, int I, int length) {while (I >= 0) {for (int j = 2 * I + 1; j <= length; J = {j * 2 + 1) / / j for left subtree if at this time (j + 1 < = length && a [j] < a [m + 1]) {/ / if the left subtree is greater than the right subtree, then move the pointer, pointing to the right subtree j++; } if (a[I] < a[j]) {int temp = a[I]; a[i] = a[j]; a[j] = temp; } } i--; }} private static void sort(int[] a) {private static void sort(int[] a) { length > 0; length--) { heapSort(a, length / 2 - 1, length); Int temp = a[0]; a[0] = a[length]; a[length] = temp; }}}Copy the code
Improved version (logically better understand the teacher’s idea, but I think the complexity does not reach Nlogn)
Int j = a.length; int j = a.length; int j = a.length; int j = a.length; j > 1; j–) {}
2. Construct the big top heap idea, first use temporary variables to store the index value, and then compare the size with the subtree. When the pointer determines the location of all nodes in the node tree, compare with the value of all nodes, assign a value larger than the index, and finally place the value of the original index at the node location of the subtree
Code implementation
private static void adjustSort(int[] a) {
// Build the big top heap
for (int j = a.length; j > 1; j--) {
for (int i = a.length / 2 - 1; i >= 0; i--) {
adjustHeap(a, i, j);
}
// Swap the top element with the bottom
int temp = a[0];
a[0] = a[j - 1];
a[j - 1] = temp; }}/** * Build the big top heap (ascending) *@paramA Arrays to be processed *@paramI Non-leaf node * to be processed@paramLength Indicates the length of the array to be processed */
private static void adjustHeap(int[] a, int i, int length) {
int temp = a[i];
for (int k = 2 * i + 1; k < length; k = 2 * i + 1) {
if (k + 1 < length && a[k] < a[k+1]) {
k++;
}
if (a[k] > temp) {
a[i] = a[k];
i = k;
} else {
// If the current node is not larger than the index node, then the big top heap is formed because it is from the bottom up
break;
}
}
a[i] = temp;
}
Copy the code