This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Algorithm idea

  1. Start with the first element, which can be considered sorted

  2. Take the first unsorted element and store it in the temporary variable temp. Scan the sorted elements from back to front and compare them one by one

  3. If temp is less than the sorted element, move the element to the next position

  4. Repeat step 3 until the sorted element is found to be less than or equal to

2. Case analysis

13,15,37,89,60,39,12,109,56,72 {}

The first trip: 13 15,37,89,60,39,12,109,56,72} {temp = 15

temp>13

{37,89,60,39,12,109,56,72} temp = 37

temp>15 temp>13

{89,60,39,12,109,56,72} temp = 89

temp>37 temp>15 temp>13

{60,39,12,109,56,72} temp =60

Temp < 89:60 <->89 13,15, 37, 60, 89 {39,12,109,56,72}

temp>37 temp>15 temp>13

{39,12,109,56,72} temp = 39

Temp < 89:39 <->89 13,15, 37, 60,39,89 {12,109,56,72}

Temp < 60:39 <->60 13,15, 37, 39, 60, 89 {12,109,56,72}

temp>37 temp>15 temp >13

{12,109,56,72} temp = 12

Temp < 89:12 <->89 13,15, 37, 39,60, 12, 89 {109,56,72}

Temp < 60:12 <->60 13,15, 37, 39,12,60,89 {109,56,72}

Temp < 39:12 <->39 13,15, 37, 12, 39, 60, 89 {109,56,72}

Temp < 37:12 <->37 13,15, 12, 37, 39,60,89 {109,56,72}

Temp < 15:12 <->15 13,12,15, 37, 39,60,89 {109,56,72}

Temp < 13:12 <->13 12, 13, 15, 37, 39,60,89 {109,56,72}

{109,56,72} temp = 109

…

3. Algorithm code

import java.util.Arrays;

/** * insert sort *@author xcbeyond
 *
 */
public class InsertSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[] ={13.15.37.89.60.39.12.109.56.72}; a = insertSort(a); String s = Arrays.toString(a); System.out.println(s); }public static int[] insertSort(int[] ary){
		for(int i = 1; i < ary.length; i++){int temp = ary[i];
			int j;
			for(j = i-1; j>=0&& temp < ary[j]; j--){ ary[j+1] = ary[j];
			}
			ary[j+1] = temp;
		}
		
		returnary; }}Copy the code

Another (easy to understand) :

import java.util.Arrays;

/** * insert sort *@author xcbeyond
 *
 */
public class InsertSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[] ={13.15.37.89.60.39.12.109.56.72}; a = insertSort(a); String s = Arrays.toString(a); System.out.println(s); }public static int[] insertSort(int[] ary){
		for(int i = 1; i < ary.length; i++){int temp = ary[i];
			int j;
			for(j = i-1; j>=0; j--){if(temp < ary[j]){
					ary[j+1] = ary[j];
				}
				else
					break; // Find the insertion position
			}
			ary[j+1] = temp;
		}
		
		returnary; }}Copy the code