Fourteen common Java algorithms

1, Briefly list 14 common algorithms in Java

Serial numberabbreviationenglishbrief introduction
1Binary search methodBinary Search

Binary search requires that the linear table must adopt the sequential storage structure, and the elements in the table are arranged in order by keywords.

2Bubble sort algorithm Bubble SortIt repeatedly visits the element column to be sorted and compares two adjacent elements in turn element , if the order (e.g. from big to small, from Z to A) is wrong, exchange them. The work of visiting elements is repeated until no adjacent elements need to be exchanged, that is, the element column has been sorted.
3Insertion sorting algorithmInsertion sort
By constructing an ordered sequence, for unordered data, scan from back to front in the sorted sequence, find the corresponding position and insert it.
4Quick sorting algorithmQuick sortAn improvement of bubbling algorithm. It 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.
5Hill sorting algorithmShell's Sort

Hill sort is a kind of insertion sort, also known as "reduced incremental sort", which is a more efficient improved version of direct insertion sort algorithm. Hill sorting is an unstable sorting algorithm

6Merge sort algorithm Merge SortMerge sort is an effective and stable sort algorithm based on merge operation. This algorithm is a very typical application of divide and conquer method. 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 merged into one, it is called two-way merging.
7Bucket sorting algorithmBucket sortBucket sorting is also called box sorting. The working principle is to divide the array into a limited number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or continue to use bucket sorting recursively). Bucket sorting is an inductive result of pigeon nest sorting. Bucket sorting uses linear time when the values in the array to be sorted are evenly distributed( Θ (n)). However, bucket sorting is not a comparative sorting. It is not affected by the lower limit of O(n log n).
8Cardinality sorting algorithmRadix SortCardinal sort belongs to "distribution sort", also known as "bucket sort" or bin sort. As the name suggests, it allocates the elements to be sorted to some "buckets" through some information of key values, so as to achieve the function of sorting. Cardinal sort belongs to stable sort, and its time complexity is O (nlog(r)m), where r is the cardinality adopted and M is the number of heaps, In some cases, the efficiency of cardinal ranking method is higher than that of other stable ranking methods.
9Pruning algorithmpruning algorithmsIn the optimization of search algorithm, pruning is to avoid some unnecessary traversal process through some judgment. In image, it is to cut some "branches" in the search tree, so it is called pruning. The core problem of application pruning optimization is to design pruning judgment method, that is, to determine which branches should be abandoned and which branches should be retained.
10Backtracking algorithmBacktrackingBacktracking algorithm is actually a search attempt process similar to enumeration. It is mainly to find the solution of the problem in the search attempt process. When it is found that the solution conditions are not met, it will "backtrack" back and try other paths.
11Shortest path algorithmThe path from a vertex to another vertex along the edge of the graph is called the shortest path. There are the following algorithms to solve the shortest path problem: Dijkstra algorithm, Bellman Ford algorithm, Floyd algorithm and SPFA algorithm.
12Maximum subarray algorithm
13Longest common suborder algorithm
14Minimum spanning tree algorithm

2, Specific introduction

1. Binary search method

(1) Algorithm principle:

It is also called half search, which requires the sequence to be searched to be orderly. Take the value of the middle position every time and compare it with the keyword to be checked. If the middle position
If the value of is larger than the keyword to be checked, the search process is cycled in the first half. If the value in the middle is smaller than the keyword to be checked,
Then loop the search process in the second half. Until it is found, there are no keywords to be checked in the sequence.
(2) Code example:
/**
 * Binary search
 * @param srcArray Source array
 * @param des Target element
 * @return If it is found, the index position is returned, and if it is not found, - 1 is returned
 */
public static int binarySearch(int[] srcArray, int des) {
    //Define initial minimum and maximum indexes
    int start = 0;
    int end = srcArray.length - 1;
    //Make sure that there are no duplicate lookups and out of bounds
    while (start <= end) {
        //Calculate the intermediate index value > > > logical right shift, that is, int middle = (end + start)/2
        int middle = (end + start)>>>1 ;//Prevent overflow

        if (des == srcArray[middle]) {
            return middle;
            //Lower limit of judgment
        } else if (des < srcArray[middle]) {
            end = middle - 1;
            //Upper limit of judgment
        } else {
            start = middle + 1;
        }
    }
    //If not, - 1 is returned
    return -1;
}

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-------

Tags: Algorithm

Posted by teeba on Sun, 17 Apr 2022 13:37:28 +0930