Java writes insertion sort algorithm and outputs results

Sample code and running results of Java implementation of insertion sort

Insertion sort is a simple and commonly used sorting algorithm that is widely used in practical applications. This article will introduce how to use Java language to implement insertion sort, and give corresponding code examples and running results.

The basic idea of ​​insertion sort is to divide the array to be sorted into two parts: sorted and unsorted. Initially, the sorted part has only one element, and then the elements of the unsorted part are inserted into the sorted part. appropriate position until all elements are inserted.

The following is a sample code for implementing insertion sort in 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 -= 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 10, 8, 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();
    }
}

The insertionSort method in the code implements the insertion sort algorithm. It uses an outer loop to iterate through each element of the unsorted part, inserting the element into the appropriate position in the sorted part. The inner loop searches for a suitable insertion position in the sorted part and moves elements larger than the current element back.

In the main method, we define an integer array arr and initialize a set of unordered elements. First, the array before sorting is output, then the insertionSort method is called to sort, and finally the sorted array is output.

The running results are as follows:

排序前：
5 2 10 8 3 
排序后：
2 3 5 8 10 

It can be seen that after processing by the insertion sort algorithm, the original unordered array has been successfully sorted from small to large.

The time complexity of insertion sort is O(n^2), and its performance is better when processing small-scale data sets. However, for large-scale data sets, the performance of insertion sort will drop significantly and is not as good as other efficient sorting algorithms. Therefore, in actual development, it is necessary to choose a suitable sorting algorithm according to the specific situation.

The above is the detailed content of Java writes insertion sort algorithm and outputs results. For more information, please follow other related articles on the PHP Chinese website!