Insert sort principle and Java implementation

由King Wang

1 月 3, 2022 code

The basic idea ：

The sorting sequence is divided into two parts , That is to say, it is already in sequence and waiting to be sorted ; Every time from the rest n-1 Among them , Take out the number and sequence from back to front , According to the sorting rules （ From small to large ）, Compare the extracted number with the larger number and move backward , Until we find the right position , We will continue with a new round of comparison .

Illustrate with examples ：

Code implementation ：

import java.util.Arrays;
public class InsertSort {
public static void insertSort(int[] a) {
int i , j, key;// The data to be inserted
for(j=1; j < a.length; j++) {// Control a new round to insert , The number to compare
key = a[j];
i = j - 1;
while( i >= 0 && key < a[i]) {// control 、 Compare the insertion position
a[i+1] = a[i];
i--;
}
a[i+1] = key;
}
}
public static void main(String[] args) {
int a[] = {42,38,57,69,13,27,49};// Array to sort
insertSort(a);
System.out.println(Arrays.toString(a));// Print
}
}