Sorting, dichotomy

1. Sort

Sorting means that the saved elements are stored according to certain rules

For example, the grades are sorted in descending order , Top three in the class , Just take the first three data

1.1 Bubble sort

  

1.2 Selection sort

public static void selectSort(int[] arr) {
            int count = 0;
            int change = 0;
            for (int current = 0; current < arr.length - 1; current++) {
                // hypothesis The current element Is the smallest
                int min = current;
                // current+1 Because There is no need to compare yourself
                for (int i = current + 1; i < arr.length; i++) {
                    count++;
                    // Determine whether there are other elements than min It's still small
                    if (arr[min] < arr[i]) {
                        // If there is Just compare this to min Small element subscript , Assign a value to min
                        min = i;
                        change++;
                    }
                }
                // Judge At present current Elements Is it the smallest
                if (min != current) {
                    // If the first element is not the smallest , Just transpose this element with the smallest element
                    int temp = arr[current];
                    arr[current] = arr[min];
                    arr[min] = temp;
                }
            }
            System.out.println(" Select sort complete , perform "+count+" Time , transposition "+change+" Time ");
        }

2. Look for the element

1. Find data , For example, you need to find one in a pile of data and return its index , No return found -1

The return value is boolean; It's just true Fake is false

Return to digital ： For example, return index , If you can find it, return to the index , Return if you can't find it -1

Reference type ： It is the object , Fake is null

2.1 In order to find

 2.2  Two points search

// Two points search Also known as half search   The demand data is in order
public static int binarySearch(int arr[], int target){
    int count=0;
//    1. Determine the start and end and intermediate data
    int startIndex=0;
    int endIndex=arr.length-1;
    int m=(startIndex+endIndex)/2;
// Cycle comparison
while(startIndex<=endIndex){
    count++;
//     If the target data is equal to the intermediate data , Return the index of intermediate data
    if(target==arr[m]){
        System.out.println(" Executed "+count+" Time ");
        return m;
        
    }
//     If the target data is larger than the intermediate data , Then continue to search in the second half , start = middle +1, End unchanged , Then generate intermediate data
    if(target>arr[m]){
        startIndex=m+1;
    }else {
//         If it is less than , Take the first half , Initial invariance , end = middle -1, Then generate intermediate data
            endIndex=m-1;
        }
//     Generate intermediate data
m=(startIndex+endIndex)/2;    
}
// Can be implemented here , Indicates that there is no
System.out.println(" Yes "+count+" Time ");
return -1;
    }