Link: https://www.cnblogs.com/yolandaBlog/p/9188149.html

Sort out the commonly used and basic algorithms. As the usual projects are relatively simple, algorithms are rarely used, but the work is not only in front of us, but also poetry and distance.

1. Linked list

Linked list is used to store data and is composed of a series of nodes. The physical addresses of these nodes are not necessarily continuous, that is, they may or may not be continuous, but the nodes in the linked list are orderly. A node consists of the value of the data and the address of the next data. The data types in a linked list can be various. Arrays are also used to store data. Compared with linked lists, the length needs to be determined during initialization. The data in an array is of the same type. In Java, ArrayList is implemented through arrays, while LinkedList is implemented through linked lists. A simple linked list class is as follows:

 1 public class Node{
 2       private Object data;
 3   
 4       private  Node next;
 5   
 6       public Node(Object data){
 7                 this.data = data;
 8        }
 9   
10      //Omit set and get methods
11 }

2. Binary tree

Binary tree is an ordered set of n (n > = 0) nodes. Each node has at most two child nodes, namely, the left node and the right node, and the order of the left and right nodes cannot be changed.

When n=0, it is an empty binary tree; When n=1, it is a binary tree with only one root.

 1 public class BinTree {
 2     
 3     private BinTree lChild;//Left node
 4     
 5     private BinTree rChild;//Right node 
 6     
 7     private Object data; //Data domain  
 8 
 9     public BinTree getlChild() {
10         return lChild;
11     }
12 
13     public void setlChild(BinTree lChild) {
14         this.lChild = lChild;
15     }
16 
17     public BinTree getrChild() {
18         return rChild;
19     }
20 
21     public void setrChild(BinTree rChild) {
22         this.rChild = rChild;
23     }
24 
25     public Object getData() {
26         return data;
27     }
28 
29     public void setData(Object data) {
30         this.data = data;
31     }
32     
33 }

3. Sorting

(1) Bubble sorting

Repeatedly visit the sequence to be sorted, compare two elements at a time, and exchange them if they are in the wrong order. The work of visiting the sequence is repeated until there is no need to exchange, that is, the sequence has been sorted. Time complexity O (n) ²)， It is a stable algorithm.

Compare the numbers in turn, and put the large (or small) ones behind the net, as follows:

 1     public static void bubbleSort(int []arr) {
 2         for(int i =0;i<arr.length-1;i++) {
 3             for(int j=0;j<arr.length-i-1;j++) {  //-1 to prevent overflow
 4                 if(arr[j]>arr[j+1]) {  //Put the big numbers in the back
 5                     int temp = arr[j];
 6                      
 7                     arr[j]=arr[j+1];
 8                      
 9                     arr[j+1]=temp;
10             }
11             }    
12         }
13     }

(2) Quick sort

The data to be sorted is divided into two independent parts through one-time sorting. All the data in one part is smaller than all the data in the other part, and then the two parts of data are quickly sorted according to this method. The whole sorting process can recursion In order to make the whole data orderly sequence.

1     public static void quickSort(int[] numbers,int low,int high){
2         if(low < high) {
3         　　int middle = getMiddle(numbers,low,high); //Divide the numbers array into two
4         　　quickSort(numbers, low, middle-1);   //Recursively sort low field tables
5         　　quickSort(numbers, middle+1, high); //Recursively sort high field tables
6         }
7     
8     }

(3) Select sort

Each time from the to be sorted data elements The smallest (or largest) element is selected and stored at the beginning of the sequence until all the data elements to be sorted are arranged. Selective sorting is an unstable sorting method (for example, the sequence [5, 5, 3] exchanges the first [5] with [3] the first time, causing the first 5 to move behind the second 5).

 1 public static void selectSort(int[]a){
 2     int minIndex=0;
 3     int temp=0;
 4 
 5     for(int i=0;i<a.length-1;i++) {
 6         minIndex=i;//Minimum data array subscript of unordered area
 7         for(intj=i+1;j<a.length;j++) {
 8             //Find the smallest data in the unordered area and save its array subscript
 9             if(a[j]<a[minIndex]) {
10                 minIndex=j;
11             }
12         }
13         //Put the smallest element at the front of this loop
14         temp=a[i];
15         a[i]=a[minIndex];
16         a[minIndex]=temp;
17     }
18 }

(4) Insert sort

In each step, a record to be sorted is inserted into the appropriate position of the previously sorted word sequence according to its sequence code size (after finding the appropriate position from back to front) until all the records are inserted and sorted.

Each number is compared with the number in front of it, because the order of the number in front is already arranged

 1 private static int[] insertSort(int[]arr){
 2     for(int i=1;i<arr.length;i++){
 3         for(int j=i;j>0;j--){
 4             if(arr[j]<arr[j-1]){
 5                 int temp=arr[j];
 6                 arr[j]=arr[j-1];
 7                 arr[j-1]=temp;
 8              }else{
 9                  break;
10             }
11         }
12       }
13      return arr;
14 }

(5) Hill sort

The records are grouped according to a certain increment of subscript, and each group is sorted by direct insertion sorting algorithm; As the increment decreases, each group contains more and more keywords. When the increment decreases to 1, the whole file is divided into one group, algorithm It ends.

 1 public static void main(String [] args)
 2 {
 3     int[]a={49,38,65,97,76,13,27,49,78,34,12,64,1};
 4         //Shell Sort 
 5         int d=a.length;
 6             while(true){
 7                 d=d/2;
 8                 for(int x=0;x<d;x++){
 9                     for(int i=x+d;i<a.length;i=i+d){
10                         int temp=a[i];
11                         int j;
12                         for(j=i-d;j>=0&&a[j]>temp;j=j-d){
13                             a[j+d]=a[j];
14                         }
15                         a[j+d]=temp;
16                     }
17                 }
18                 if(d==10){
19                     break;
20                 }
21             }
22 }

(6) Merge sort

An effective sorting algorithm based on merging operation, which is a very typical application of Divide and Conquer. Merge the ordered subsequences to obtain a completely ordered sequence; That is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are combined into one ordered table, it is called two-way Merge . Time complexity O(n log n).

 1     public static int[] sort(int[] nums, int low, int high) {
 2         int mid = (low + high) / 2;
 3         if (low < high) {
 4             // left
 5             sort(nums, low, mid);
 6             // right
 7             sort(nums, mid + 1, high);
 8             // Left and right merging
 9             merge(nums, low, mid, high);
10         }
11         return nums;
12     }

(6) Heap sort

Using stacked trees (heaps) data structure Designed by Sorting algorithm , it is a kind of selective sorting. Can use array The feature is to quickly locate the elements of the specified index. (not understood for the time being)

4. Recursion and iteration
Recursion is to call itself until the conditions for ending recursion are met. Iteration is a continuous cycle, which ends directly. Generally speaking, if you can use iteration, you don't need recursion, which consumes a lot of resources.

 1 recursion
 2 int recursion(...){
 3     if(...) {  //Recursive termination condition
 4         return abc(...); 
 5     }
 6     return 0;
 7 }
 8 
 9 iteration
10 int iteration(...){
11     for(; ; ;) {    //Iteration termination condition
12         a = b + c;
13     } 
14 }

5. Bit operation

Bit operations and logical operators are two different things. When I first learned them, I often couldn't remember them clearly. There are 6 kinds of bit operations, namely and (&), or (|), XOR (^), inversion (~), shift left (<), shift right (> >). Among these bit operators, only negation (~) is the barrage operator, and the other five are binocular operators.

6. Probability

7. Arrangement and combination