1, Briefly list 14 common algorithms in Java

2, Specific introduction

1. Binary search method

(1) Algorithm principle:

2. Bubble sorting algorithm

(1) Algorithm principle:
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. At this point, the last element should be the largest 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 example:

public static void bubbleSort(int 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;
            }
        }
    }
}

public static void bubbleSort2(int[] a, int n) {
    int i, j;
    for (i = 0; i < n; i++) {//Indicates n sorting processes.
        for (j = 1; j < n - i; j++) {
            if (a[j - 1] > a[j]) {//If the preceding number is greater than the following number, it will be exchanged
                //Exchange a[j-1] and a[j]
                int temp;
                temp = a[j - 1];
                a[j - 1] = a[j];
                a[j] = temp;
            }
        }
    }
}

3. Insertion sorting algorithm

(1) Concept: by constructing an ordered sequence, for unordered data, scan from back to front in the sorted sequence, find the corresponding position and insert it.

(2) A popular metaphor:

Insertion sorting is similar to sorting out playing cards when fighting landlords. When touching a card for the first time, the left hand is empty. After that, every time you touch a card and insert it into the card on the left hand, you will compare this card with the cards in order in the left hand from right to left to confirm the position of this card.

public static void insertionSort(int arr[]) {
    for (int i = 1; i < arr.length; i++) {
        //Number of inserts
        int insertVal = arr[i];
        //Position inserted (prepare to compare with the previous number)
        int index = i - 1;
        //If the number inserted is smaller than the number inserted
        while (index >= 0 && insertVal < arr[index]) {
            //Will move arr[index] backward
            arr[index + 1] = arr[index];
            //Move the index forward
            index--;
        }
        //Put the inserted number in the right place
        arr[index + 1] = insertVal;
    }
}

4. Quick sorting algorithm

(1) Concept: quick sort refers to dividing the data to be sorted 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 quickly sort the two parts of data according to this method. The whole sorting process can be carried out recursively, so that the whole data becomes an ordered sequence.

(2) Quick sort process diagram:

Select a key value as the reference value. Those smaller than the benchmark value are in the left sequence (generally disordered), and those larger than the benchmark value are in the right sequence (generally disordered).

——Pictures from the Internet

(3) Code example:

/**
 * Quick sort
 *
 * @param arr   Array to be sorted
 * @param start Minimum index of array: 0
 * @param end   Maximum index of array: arr.length - 1
 * @return Sorted array
 */
public static int[] quickSort(int arr[], int start, int end) {
    int pivot = arr[start];
    int i = start;
    int j = end;
    while (i < j) {
        while ((i < j) && (arr[j] > pivot)) {
            j--;
        }
        while ((i < j) && (arr[i] < pivot)) {
            i++;
        }
        if ((arr[i] == arr[j]) && (i < j)) {
            i++;
        } else {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    if (i - 1 > start) arr = quickSort(arr, start, i - 1);
    if (j + 1 < end) arr = quickSort(arr, j + 1, end);
    return (arr);
}

/**
 * Quick sort (no return value)
 * @param a Array to be sorted
 * @param low Minimum index of array: 0
 * @param high Maximum index of array: arr.length - 1
 */
public static void quickSort2(int[] a, int low, int high) {
    int start = low;
    int end = high;
    int key = a[low];
    while (end > start) {
        //Compare from back to front
        while (end > start && a[end] >= key)
            //If there is nothing smaller than the key value, compare the next one until there is an exchange position smaller than the key value, and then compare from front to back
            end--;
        if (a[end] <= key) {
            int temp = a[end];
            a[end] = a[start];
            a[start] = temp;
        }
        //Compare from front to back
        while (end > start && a[start] <= key)
            //If there is no one larger than the key value, compare the next one until there is an exchange position larger than the key value
            start++;
        if (a[start] >= key) {
            int temp = a[start];
            a[start] = a[end];
            a[end] = temp;
        }
        //At this time, the first cycle comparison is over, and the position of the key value has been determined. The values on the left are smaller than the key values, and the values on the right are larger than the key values, but the order of the two sides may be different. Make the following recursive call
    }
    //recursion
    if (start > low) quickSort2(a, low, start - 1);//Left sequence. First index position to key index - 1
    if (end < high) quickSort2(a, end + 1, high);//Right sequence. From key index + 1 to last
}

5. Hill sorting algorithm

(1) Basic idea: first divide the whole record sequence to be sorted into several subsequences for direct insertion sorting. When the records in the whole sequence are "basically orderly", then directly insert and sort all records in turn.

(2) Code example:

/**
 * Shell Sort 
 * @param a 
 */
private static void shellSort(int[] a) {
    int dk = a.length / 2;
    while (dk >= 1) {
        //It is similar to insert sort, except that the increment of insert sort is 1, where the increment is dk. Just replace 1 with dk
        for (int i = dk; i < a.length; i++) {
            if (a[i] < a[i - dk]) {
                int j;
                int x = a[i];//x is the element to be inserted
                a[i] = a[i - dk];
                for (j = i - dk; j >= 0 && x < a[j]; j = j - dk) {
                    //Through the cycle, move back one by one to find the position to be inserted.
                    a[j + dk] = a[j];
                }
                a[j + dk] = x;//insert
            }
        }
        dk = dk / 2;
    }
}

6. Merge sort algorithm

(1) Basic idea: Merge sorting method is to combine two (or more) ordered tables into a new ordered table, that is, the sequence to be sorted is divided into several subsequences, and each subsequence is ordered. Then the ordered subsequences are combined into an overall ordered sequence.

(2) Merge sort: it is an effective and stable sort algorithm based on merge operation.

What is merge operation?

Merging operation, also known as merging algorithm, refers to the method of merging two sequential sequences into one sequential sequence.
as　With sequence{6，202，100，301，38，8，1}
Initial state: 6,202,100,301,38,8,1
 After the first merger:{6,202},{100,301},{8,38},{1}，Comparison times: 3;
After the second merger:{6,100,202,301}，{1,8,38}，Comparison times: 4;
After the third merger:{1,6,8,38,100,202,301},Comparison times: 4;
The total number of comparisons is: 3+4+4=11；
The number in reverse order is 14;

(2) Code example:

/**
 * Merge sort
 * @param nums Array to be sorted
 * @param l Start index: 0
 * @param h Maximum index: num length - 1
 * @return Sorted array
 */
public static int[] mergeSort(int[] nums, int l, int h) {
    if (l == h)
        return new int[]{nums[l]};

    int mid = l + (h - l) / 2;
    int[] leftArr = mergeSort(nums, l, mid); //Left ordered array
    int[] rightArr = mergeSort(nums, mid + 1, h); //Right ordered array
    int[] newNum = new int[leftArr.length + rightArr.length]; //New ordered array

    int m = 0, i = 0, j = 0;
    while (i < leftArr.length && j < rightArr.length) {
        newNum[m++] = leftArr[i] <= rightArr[j] ? leftArr[i++] : rightArr[j++];
    }
    while (i < leftArr.length)
        newNum[m++] = leftArr[i++];
    while (j < rightArr.length)
        newNum[m++] = rightArr[j++];
    return newNum;
}

7. Bucket sorting algorithm

(1) Basic idea: divide the array arr into n sub intervals (buckets) of the same size, sort each sub interval separately, and finally merge. Counting sorting is a special case of bucket sorting, which can be regarded as the case where there is only one element in each bucket.

(2) Sorting process:

1. Find the maximum value max and minimum value min in the array to be sorted
2. We use the dynamic array ArrayList as the bucket, and the elements in the bucket are also stored in ArrayList. The number of barrels is (maxmin)/arr.length+1
3. Traverse the array arr and calculate the bucket of each element arr[i]
4. Each bucket is sorted separately

(3) Code example:

/**
 * Bucket sorting
 *
 * @param data Array to be sorted
 */
public static void bucketSort(int data[]){
    int n = data.length;
    int bask[][] = new int[10][n];
    int index[] = new int[10];
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        max = max > (Integer.toString(data[i]).length()) ? max : (Integer.toString(data[i]).length());
    }
    String str;
    for (int i = max - 1; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            str = "";
            if (Integer.toString(data[j]).length() < max) {
                for (int k = 0; k < max - Integer.toString(data[j]).length(); k++)
                    str += "0";
            }
            str += Integer.toString(data[j]);
            bask[str.charAt(i) - '0'][index[str.charAt(i) - '0']++] = data[j];
        }
        int pos = 0;
        for (int j = 0; j < 10; j++) {
            for (int k = 0; k < index[j]; k++) {
                data[pos++] = bask[j][k];
            }
        }
        for (int x = 0; x < 10; x++) index[x] = 0;
    }
}

8. Cardinality sorting algorithm

(1) Basic idea: cut the integer into different numbers according to the number of digits, and then compare them according to each number of digits.

(2) Sorting process: unify all values to be compared (positive integers) into the same digit length, and fill zero in front of the shorter digit. Then, start from the lowest order and sort once in turn. In this way, the sequence will become an ordered sequence from the lowest order to the highest order.

(3) Code example:

/**
 * Cardinality sort
 * @param number Array to be sorted
 * @param d Indicates the maximum number of digits
 */
public static void sort(int[] number, int d) 
{
    int k = 0;
    int n = 1;
    int m = 1; //Which bit is the sorting basis of control key values
    int[][] temp = new int[10][number.length]; //The first dimension of the array represents the possible remainder 0-9
    int[] order = new int[10]; //The array order[i] is used to represent the number of I bits
    while (m <= d) {
        for (int i = 0; i < number.length; i++) {
            int lsd = ((number[i] / n) % 10);
            temp[lsd][order[lsd]] = number[i];
            order[lsd]++;
        }
        for (int i = 0; i < 10; i++) {
            if (order[i] != 0)
                for (int j = 0; j < order[i]; j++) {
                    number[k] = temp[i][j];
                    k++;
                }
            order[i] = 0;
        }
        n *= 10;
        k = 0;
        m++;
    }
}

Unfinished to be continued-------