Methods and principles of writing insertion sort algorithm in Java

The steps and ideas of the insertion sort algorithm

Insertion sort is a simple and intuitive sorting algorithm. Its basic idea is to insert the elements to be sorted into the sorted at the appropriate position in the sequence.

The specific steps are as follows:

1. First, we divide the array into two parts: the sorted part and the unsorted part. Initially, there is only one element in the sorted part, which is the first element of the array.
2. We take out an element from the unsorted part in turn, compare it with the elements in the sorted part one by one, and find the appropriate position to insert.
3. During the comparison process, we move the elements in the sorted part backward to make room for the inserted elements.
4. Finally, we insert all the elements of the unsorted part into the appropriate positions of the sorted part, and the sorting is completed.

The following is a sample code for writing 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;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

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

    public static void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

In this code example, we define an insertionSort method, which accepts An array of integers is taken as argument and the array is inserted sorted. We use n to represent the length of the array, and use for to loop through the elements of the unsorted part. In each traversal, we save the current element arr[i] to the key variable, and then traverse the sorted part forward to find the appropriate position to insert key. During the comparison process, we move the larger element back one position to make room for key. Finally, we insert key into the correct position and the sorting is completed.

In the main method, we initialize an integer array arr and call the insertionSort method to sort the array. Finally, we call the printArray method to print the sorted array.

By running the above code, you can get the following output:

原数组：
5 2 8 1 9 3 
排序后的数组：
1 2 3 5 8 9 

The time complexity of the insertion sort algorithm is O(n^2), where n is the length of the array. Although the insertion sort algorithm has a high time complexity, its implementation is simple and suitable for small-scale array sorting. At the same time, in practical applications, the insertion sort algorithm also has the characteristics of stability.

The above is the detailed content of Methods and principles of writing insertion sort algorithm in Java. For more information, please follow other related articles on the PHP Chinese website!