How to implement insertion sort algorithm in Java?

1. Basic idea

The algorithm description of insertion sort (Insertion-Sort) is a simple and intuitive sorting algorithm. It works by constructing an ordered sequence. For unsorted data, it scans from back to front in the sorted sequence, finds the corresponding position and inserts it.

2. Algorithm analysis

1. Algorithm description

Generally speaking, insertion sort is implemented on the array using in-place. The specific algorithm is described as follows:

• Starting from the first element, the element can be considered to have been sorted;

• Take out the next element, Scan from back to front in the sorted element sequence;

• If the element (sorted) is larger than the new element, move the element to the next position;

• Repeat step 3 until you find a position where the sorted element is less than or equal to the new element;

• Insert the new element into that position;

• Repeat steps 2~5.

2. Process analysis

(1) Mark the first element (1) as sorted.

(2), extract the first unsorted element (28).

(3) Find the place where the extracted element is inserted; compare it with the sorted element 1.

(4), 1 > 28 is not true (False), insert an element at the existing position.

(5). Find the place where the extracted elements are inserted; compare with the sorted elements 28.

(6), 28 > 3 If true (True), the currently sorted element ({val1}) will be moved 1 space to the right.

(7) Find the place where the extracted element is inserted; compare it with the sorted element 1.

(8), 1 > 3 is not true (False), insert an element at the existing position.

(9), and so on

3. Algorithm implementation

package com.algorithm.tenSortingAlgorithm;

import java.util.Arrays;

public class InsertionSort {
    private 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;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,28,3,21,11,7,6,18};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

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