How to implement insertion sort algorithm using java

How to use Java to implement the insertion sort algorithm

Insertion sort is a simple but effective sorting algorithm based on the idea of ​​comparing and exchanging elements. In this article, we will learn how to write an implementation of the insertion sort algorithm in Java and provide concrete code examples.

The basic idea of ​​insertion sort is to divide the array into sorted and unsorted parts. First, we treat the first element as the sorted part, and then insert the elements of the unsorted part into the correct position of the sorted part in sequence. In order to find the correct insertion position, we need to compare the current element with the elements of the sorted part one by one, and gradually move the elements of the sorted part backward until we find a suitable insertion position. By repeating this process, the entire array is finally sorted.

The following is a sample code for implementing the insertion sort algorithm using Java:

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, 3, 1};
        System.out.println("原始数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

        insertionSort(arr);

        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

In this example, we define a static method named insertionSort, which accepts a Array of integers as parameters. We use a loop to go through the elements of the unsorted part and insert them into the correct position of the sorted part. The inner while loop is used to move the elements of the sorted section backward until the correct insertion position is found. Finally, we create a sample array in the main method and call the insertionSort method to sort it. Finally, we output the sorted array to the console.

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

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

As you can see, the insertion sort algorithm successfully sorted the original array.

Summary:
This article introduces how to use Java to write the implementation of the insertion sort algorithm, and provides specific code examples. Insertion sort is a simple but effective sorting algorithm that achieves sorting by dividing the array into sorted and unsorted parts and comparing and moving elements one by one. By understanding the idea and code implementation of the insertion sort algorithm, we can flexibly apply this sorting algorithm in actual programming projects.

The above is the detailed content of How to implement insertion sort algorithm using java. For more information, please follow other related articles on the PHP Chinese website!