第一种方法:
插入数值替换方式:从后往前替换
复制代码
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
52package 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
44package 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
46package 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; } } } }
最后
以上就是顺利芝麻最近收集整理的关于直接插入排序的两种方法的全部内容,更多相关直接插入排序内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复