第一种方法：

插入数值替换方式：从后往前替换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package com.bhy.test_sort;

/**
 * 插入排序---方法1---从后往前替换
 * 
 * @author bhy 
 * 2018-08-03
 */
public class InsertSort {
	
	private int[] arr;
	
	public InsertSort(int[] arr) {
		this.arr = arr;
	}
	
	/**
	 * 
	 *	 插入排序--记录原替换位置j的值，将插入的值i赋值给原替换位置j的值，循环替换j+1~i的值。
	 * 	【注】使用两个变量循环替换，
	 * 	 m:循环前--先记录原替换位置j的值 	m = arr[j];
	 * 	 n:循环中--记录每次j2+1的值 	 	n = arr[j2+1];  	(初始循环j2 = j)
	 * 	 arr[j2+1] = m;				//将arr[j2]赋值给arr[j2+1];
	 * 	  每次循环后 m = n;				//更新 m 值，即: 替换arr[j2]为 arr[j2+1]，准备下次循环;
	 */
	public void insert(){
		int n;
		int m;
		for (int i = 1; i < arr.length; i++) {
					
			for (int j = 0; j < i; j++) {
				
				if(arr[i] < arr[j]) {
					//保存需要替换的比较值 arr[j]
					m = arr[j];
					//先将插入值arr[i] 与比较值 arr[j] 替换
					arr[j] = arr[i];
					//循环 两两互换arr[j+1]~arr[i]的值
					for (int j2 = j ;j2 < i; j2++) {	
						n = arr[j2+1];
						arr[j2+1] = m;
						m = n;
						
					}
					break;
				}
			}		
		}			
	}

}

插入数值替换方式：从前往后替换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package com.bhy.test_sort;

/**
 * 插入排序---方法1---从前往后替换
 * 
 * @author bhy 
 * 2018-08-03
 */
 
public class InsertSort2 {
	
	private int[] arr;
	
	public InsertSort2(int[] arr) {
		this.arr = arr;
	}
	/**
	 * 
	 * 	插入排序--记录将插入的值，循环替换j+1~i的值后，将插入值赋值给原替换位置的值。
	 *  n: 记录将插入的值arr[i];
	 */
	public void insert(){
		int n;
		for (int i = 1; i < arr.length; i++) {
					
			for (int j = 0; j < i; j++) {
				
				if(arr[i] < arr[j]) {
					//记录arr[i]的值
					n = arr[i];
					for (int j2 = i ; j2 > j ; j2--) {	
						arr[j2] = arr[j2-1];
						
					}
					//替换arr[i]与arr[j]
					arr[j] = n;
					break;
				}
			}	
		}
	}
	
}

第二种方法（改进）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package com.bhy.test_sort;
/**
 * 插入排序---方法2
 * 
 * @author bhy 
 * 2018-08-03
 */
public class ProInsertSort {

    public static void main(String[] args){
        int[] x = { 6, 2, 7, 1, 5, 9 };
        insertion_sort(x);
        for (int i = 0; i < x.length; i++) {
			System.out.print(x[i]+" ");
		}
    }
	/**
	 * 
	 *	插入排序--改进
	 *  从下标为1开始，记录i的值，并循环比较i与i-1的大小
	 * 	如: i<i-1时替换i的值为i-1值,继续比较i原值与i-2的值...依次
	 * 	直到i>=i-1时,结束i值插入，继续进行i+1的值插入
	 */
    public static void insertion_sort(int[] arr) {
		
		for (int i = 1; i < arr.length; i++) {
			//i<i-1时替换i的值为i-1值,继续比较i原值与i-2的值...依次
			if(arr[i] < arr[i-1]) {
				//记录下标为i的数值
				int value = arr[i];
				//记录下标i
				int j = i;
				//循环比较j-1下标位置的数值与待插入数值value大小，依次替换相邻的比value大的
				while(j>0 && arr[j-1]>value ) {
					arr[j] = arr[j-1];
					j--;	
				}
				//将value插入到比它大的数值的前面
				arr[j] = value;
			
			}
		}
    }

}