Detailed explanation of the insertion sort algorithm implemented in Java

Detailed explanation of the implementation method of Java insertion sort algorithm

Insertion sort is a simple and intuitive sorting algorithm. Its principle is to divide the sequence to be sorted into sorted and unsorted parts. Each time one element is taken out from the unsorted part and inserted into the appropriate position of the sorted part. The implementation method of the insertion sort algorithm is relatively simple. The specific implementation method will be introduced in detail below and corresponding code examples will be given.

1. Algorithm Idea
   Assume that an integer array arr is to be sorted in ascending order. Initially, arr[0] is regarded as the sorted part, and the remaining elements are regarded as the unsorted part. Based on this, if the current element to be inserted is arr[i] (i starts from 1), then find the position j where arr[i] should be inserted from the sorted part arr[0:i-1], and then arr[i] is inserted into position j, and all elements of arr[j:i-1] are moved backward one position in sequence.
2. Code implementation
   The following is a code example for implementing the insertion sort algorithm in Java language:

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;

            // 将已排序的元素依次向后移动，直到找到arr[i]应该插入的位置
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 3, 1};
        insertionSort(arr);
        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3. Algorithm analysis
   The time complexity of the insertion sort algorithm is O(n^2), where n is the number of elements to be sorted. In the best case, that is, the array to be sorted is already sorted, the time complexity of insertion sort is O(n). In the worst case, the array to be sorted is in reverse order, and the time complexity of insertion sort is O(n^2). Insertion sort is a stable sorting algorithm because the relative positions of equal elements do not change before and after sorting.

To sum up, this article introduces the implementation method of Java insertion sort algorithm in detail and gives corresponding code examples. Insertion sort is a simple and intuitive sorting algorithm suitable for small-scale arrays or basically ordered arrays. In practical applications, insertion sort can be replaced by other more efficient sorting algorithms, but understanding the principles and implementation methods of insertion sort is very beneficial to learning other sorting algorithms.

The above is the detailed content of Detailed explanation of the insertion sort algorithm implemented in Java. For more information, please follow other related articles on the PHP Chinese website!