1. Sort of sort
  2. Time frequency and characteristics
  3. Time complexity
  4. Bubble sort
  5. Selection sort
  6. Insertion sort
  7. Hill sorting
  8. Quick sort
  9. Merge sort
  10. Radix sort
  11. 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