How to quickly master search algorithms and sorting algorithms in Java programming

1. Search algorithm

Binary algorithm

Binary search (Binary Search), also known as half search, is an efficient search algorithm. Its basic idea is: divide the ordered array (or set) into two. If the current middle element is equal to the target element, the search is successful; if the current middle element is greater than the target element, the left half is searched; if the current middle element is less than For the target element, search for the right half. Repeat the above steps until the target element is found or the search range is empty and the search fails.

The following is a binary algorithm implemented in Java:

public static int binarySearch(int[] arr, int target) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

The above method uses a set of ordered integer arrays and a target value as parameters, and returns the index of the target value in the array; if If the target value does not exist in the array, -1 is returned.

The core of the algorithm is the while loop, which is executed repeatedly when left and right meet specific conditions:

• If mid is equal to target, mid is returned and the algorithm ends ;

• If mid is greater than target, continue searching on the left, that is, set right to mid - 1;

• If mid is less than target, Then continue searching on the right side, that is, set left to mid 1.

Each time through the loop, we use mid = left (right - left) / 2 to calculate the index of the middle element. It should be noted that we must use the form of left right and not the form of (left right) / 2, otherwise it may cause integer overflow problems.

2. Sorting algorithm

In Java, the sorting algorithm is implemented by implementing the Comparable or Comparator interface. The following are several commonly used sorting algorithms and their implementation methods:

Bubble sort

Bubble sort is a simple sorting algorithm. The idea is to constantly compare two adjacent elements, and if the order is wrong, swap positions. This process is like water bubbles rising continuously, so it is called bubble sorting.

public static void bubbleSort(int[] arr) {
    int temp;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                //交换位置
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Selection sort

The idea of ​​selection sort is to select the smallest element from the unsorted elements and put it at the end of the sorting. Each time the smallest element is found, its position is swapped with the currently unsorted first element.

public static void selectionSort(int[] arr) {
    int minIndex;
    for (int i = 0; i < arr.length - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        //交换位置
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

Insertion sort

The idea of ​​insertion sort is to insert unsorted elements into the appropriate sorted position. Select an element from the unsorted elements and traverse the sorted elements from back to front. If it is smaller than the sorted element, move one position backward and continue comparing; until you find a position smaller than the unsorted element , and then insert it at this location.

public static void insertionSort(int[] arr) {
    int preIndex, current;
    for (int i = 1; i < arr.length; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
}

Quick sort

Quick sort is a sorting algorithm based on the divide and conquer idea. It selects a pivot point, splits the array into two subarrays less than or equal to the pivot point and greater than the pivot point, and then recursively sorts the two subarrays.

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int i = left, j = right, pivot = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                arr[i++] = arr[j];
            }
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            if (i < j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = pivot;
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}

The above is the detailed content of How to quickly master search algorithms and sorting algorithms in Java programming. For more information, please follow other related articles on the PHP Chinese website!