1, Time complexity

Constant time operation

If an operation has nothing to do with the data volume of the sample and is completed within a fixed time each time, it is called Changshu operation.
For example, int a = arr[i] at this time, it is only to find the offset in the array and the number of I position. This is a constant operation, independent of the amount of data, as well as addition, subtraction, multiplication and division, bit operation, etc.
For non constant operations, to get the value of position i of the linked list, int b = list.get(i), you need to traverse until position i, which is related to the amount of data.

Time complexity is an indicator of the number of Changshu operations in an algorithm flow. It is often expressed by O (pronounced big O). Specifically, you should first be very familiar with an algorithm process, then write how many constant operations have occurred in the algorithm process, and then summarize the expression of the number of constant operations.

In the expression, as long as the high-order term, neither the low-order term nor the coefficients of the high-order term, if the remaining part is f(N), the time complexity is O(f(N)).

To evaluate the quality of an algorithm process, first look at the index of time complexity, and then analyze the actual running time under different data samples, that is, "constant term time".

2, Select sort

1. Algorithm steps

First, find the smallest (large) element in the unordered sequence and store it at the beginning of the sorted sequence.
Then continue to find the smallest (large) element from the remaining unordered elements, and then put it at the end of the sorted sequence.
Repeat step 2 until all elements are sorted.

2. Code

public class chooseSort {
    public static int [] selectSort(int [] arr){
        if (arr.length == 0 || arr.length < 2){
            return arr;
        }
        for (int i = 0; i < arr.length; i++){
            int midIndex = i;
            for (int j = i+1; j < arr.length; j++){
                //Find the smallest number
                midIndex = arr[midIndex] > arr[j] ? j : midIndex;
            }
            swap(arr,i,midIndex);
        }
        return arr;
    }
    public static void swap(int []arr,int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

3, Bubble sorting

1. Algorithm steps

Compare adjacent elements. If the first one is bigger than the second, exchange them.
Do the same for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. After this step, the last element will be the maximum number.
Repeat the above steps for all elements except the last one. Continue to repeat the above steps for fewer and fewer elements at a time until no pair of numbers need to be compared.

2. Code

public class bubbleSort {

    public static int [] bubbleSort1(int arr[]){
        if (arr.length == 0 || arr.length < 2){
            return arr;

        }
        for (int i = 0; i < arr.length-1; i++){
            for (int j = 0; j < arr.length-1-i; j++){
                if (arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    //The memory of XOR A and B must be different
//                    arr[j] = arr[j] ^ arr[j+1];
//                    arr[j+1] = arr[j] ^ arr[j+1];
//                    arr[j] = arr[j] ^ arr[j+1];
                }
            }
        }
//        For (int e = arr.length - 1; E > 0; E --) {range per round
//            For (int i = 0; I < E; I + +) {how many times per round
//                if (arr[i] > arr[i+1]){
//                    int temp = arr[i];
//                    arr[i] = arr[i+1];
//                    arr[i+1] = temp;
//                }
//            }
//        }
        return arr;
    }
    public static void main(String[] args) {
        int arr[] = {2,4,1,4,2,4,2,6};
        int arr1[] = bubbleSort1(arr);
        for (int i = 0 ; i < arr1.length;i++){
            System.out.println(arr1[i]);
        }
    }
}

4, Insert sort

1. Algorithm steps

The first element of the first sequence to be sorted is regarded as an ordered sequence, and the second element to the last element is regarded as an unordered sequence.
Scan the unordered sequence from beginning to end, and insert each scanned element into the appropriate position of the ordered sequence. (if the element to be inserted is equal to an element in the ordered sequence, insert the element to be inserted after the equal element.)

2. Code

public class insertSort {
    public static int [] insertionSort(int arr[]){
        if (arr.length == 0 || arr.length < 2){
            return arr;
        }
        //0-0 must be ordered
        //Ensure 0-1 order
        //....
        //Ensure 0 - N-1 order
        for (int i = 1; i < arr.length; i++){ //Ensure 0-i order
            for (int j = i-1; j >=0 && arr[j] > arr[j+1]; j--){
                /*Every time you compare the previous one, if the previous one is small, skip it directly
                * If arr [j] > arr [j + 1], exchange, move j forward, and compare with the new value
                * and so on
                * Until J < 0, stop*/
                swap(arr,j,j+1);
            }
        }
        return arr;
    }
    public static void swap(int []arr,int i, int j){
//        int temp = arr[i];
//        arr[i] = arr[j];
//        arr[j] = temp;
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}

5, Dichotomy and extension

1. Find out whether a number exists in an ordered array

 /*
     * In an ordered array, find whether a number exists
     */
    public static boolean Exist(int arr[], int num){
        if (arr == null || arr.length == 0){
            return false;
        }
        int L = 0;
        int R = arr.length-1;
        int mid = 0;
        while (L < R){
            mid = L + ((R - L) >> 1);
            if (num < arr[mid]){
                R = mid-1;
            }else if (num > arr[mid]){
                L = mid + 1;
            }else {
                return true;
            }
        }
        //At the end of the comparison, there is a number L or R left. At this time, l and R coincide. Just compare directly
        return arr[L] == num;
    }

2. In an ordered array, find the leftmost position of > = a number

/*
    In an ordered array, find the leftmost position of > = a number
    A tag bit is defined
    * */
    public static int Exist1(int arr[], int num){

        int L = 0;
        int R = arr.length - 1;
        int mid = 0;
        int index = -1;
        while (L < R){
            mid = L + ((R - L) >> 1);
            if (arr[mid] >= num){
                index = mid; //Mark it
                R = mid - 1; //Then go to the left to find if there is a number that meets the situation
            }else {
                L = mid + 1;
            }
        }
        return index;
    }

3. Local minimum problem

Local minimum problem==In an array, speechless, any two adjacent numbers are not equal, and finding a local minimum requires the time complexity of the algorithm to be better than O(N)

Hee hee~It shows that disorder can also be divided into two
 Local optimal value:
    The existence of local minima,
      1. Length 1, arr[0]Is the local minimum;
      2. The beginning of the array, if arr[0] < arr[1] ，arr[0]Is defined as a local minimum.
      3. The end of the array, if arr[N-1] < arr[N-2] ，arr[N-1]Is defined as a local minimum.
      4. So what's left is the array subscript 1~N-2 Between. Press again arr[i-1] < arr[i] <arr[i+1] Find a local minimum.
  Finally, the question asks to return any one.
  If you search sequentially to find a number smaller than the left and smaller than the right, your time complexity is O(N),For example, monotonically decreasing array, search to the last one.
  Using binary search, you can achieve O(logN).

 public static int Exist2(int arr[]){
        if (arr == null ||arr.length == 0){
            return -1; //Empty array
        }
        if (arr.length == 1 || arr[0] < arr[1]){
            return 0;
        }//In the first case, if the length is 1, then arr[0] is the local minimum; it is written together with the second case
        if (arr[arr.length - 1] < arr[arr.length - 2]){
            return arr.length - 1;//The third case
        }

        int L = 1;
        int R = arr.length - 2;
        int mid = 0;
        while (L < R){
            mid = L + ((R-L) >> 1);
            if (arr[mid] > arr[mid - 1]){ //It shows a downward trend on the left of mid
                R = mid - 1;
            }else if (arr[mid] > arr[mid + 1]){
                L = mid+1;
            }else {
                return mid;
            }
        }
        return L;
    }

4. Strike while the iron is hot = = force buckle 162. Find the peak value

The peak element refers to the element whose value is greater than the left and right adjacent values.
Given an input array nums，among nums[i] ≠ nums[i+1]，Find the peak element and return its index.
The array may contain multiple peaks. In this case, just return the location of any peak.
You can assume nums[-1] = nums[n] = -∞. 
Example 1: input:nums = [1,2,3,1]
output: 2
 explain: 3 Is a peak element, and your function should return its index 2.
Example 2: input:nums = [1,2,1,3,5,6,4]
output: 1 Or 5
 explain: Your function can return index 1 with a peak element of 2;
Or return index 5, whose peak element is 6.

explain: Your solution should be O(logN) Time complexity.

public static int MaxIndex(int arr[]){
        if (arr == null || arr.length == 0){
            return -1;
        }
        int L = 0;
        int R = arr.length-1;
        int mid = 0;
        while (L < R){
            mid = L + ((R-L) >> 1);
            if (arr[mid] < arr[mid + 1]){
                L = mid+1;
            }else {
                R = mid;
            }
        }
        return L;
    }

6, XOR operation and expansion

1. XOR = = = no carry operation

    Properties of XOR operation
    1)0^N == N    N^N == 0
    2)XOR operation satisfies commutative law and binding rate

2. XOR expansion

1)Swap two numbers without extra variables

 arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];

2)An array has an odd number of times and other numbers have an even number of times. How to find this number

 //In a pile of numbers, other numbers have even numbers, and one number has odd numbers,
    public static void printOddTimesNum(int [] arr){
        int ero = 0;
        for (int ch : arr){
            //Each exclusive or becomes 0 if it is the same, and the last odd and 0 exclusive or is itself
            ero ^= ch;
        }
        System.out.println(ero);
    }

3)There are two kinds of numbers in an array that appear odd times and other numbers that appear even times. How to find these two numbers

 //In a pile of numbers, there are even numbers for others, and odd numbers for two numbers
    public static void printOddTimesNum1(int [] arr){
        int ero = 0;
        for (int ch : arr){
            ero ^= ch;
        }
        //Now ero = a^b (A and b are those two odd numbers)
        //ero != 0
        //One of the ero positions must be 1
        int rightOne = ero & (~ero + 1);//Take out the rightmost 1

        int ero1 = 0;
        for (int ch1 : arr){
            if ((ch1 & rightOne) == 0){
                ero1 ^= ch1;
            }
        }
        System.out.println(ero1+" "+(ero1^ero));

    }

7, Recursive behavior and estimation of time complexity

1. Use recursive method to find the maximum value in an array

public static int process(int arr[],int L, int R){
        if (L == R){
            return arr[L];
        }
        int mid = L + ((R - L)>>1);
        int leftMax = process(arr,L,mid);
        int rightMax = process(arr,mid+1,R);
        return Math.max(leftMax,rightMax);
    }

2. Use of master formula = = = when the subproblem scale is the same

  **T(n) = a * T(N / b) + O(n ^ d)**
  a This table is called several times, b Indicates the size of the subproblem, O(n^d)Represents the time complexity of other tasks
  1) log(b,a) > d -> Complexity is O(N^log(b,a)) 
  2) log(b,a) = d -> Complexity is O(N^d * logN) 
  3) log(b,a) < d -> Complexity is O(N^d)
  Supplementary reading:[Supplementary reading](http://www.gocalf.com/blog/algorithm-complexity-and-master-%20theorem.html)