算法入门-插入排序算法
插入排序算法
输入：n个数<a1,a2,a3,.....,an>。
输出：输入序列的一个排序(即重新排序)<a1',a2',a3',.......,an'>，使得a1'≤a2'≤a3'≤.......≤an'。下面给出我自己的代码实现：
代码中要排序的数组是通过方法createRandomArray()生成的。
1 /**
2 *
3 */
4 package com.b510.algorithms;
5
6 import java.util.Random;
7
8 /**
9 * 插入排序算法
10 * @author hongten(hongtenzone@foxmail.com)<br>
11 * @date 2013-6-7
12 */
13 public class PartTwoAlgorithms {
14
15 /**
16 * 降序排列
17 */
18 public static final int SORT_DESC = 1;
19 /**
20 * 升序排列
21 */
22 public static final int SORT_DES = 0;
23
24 public static void main(String[] args) {
25 int[] a = createRandomArray(6);
26 System.out.println("要进行插入排序的数组为：" + printAnArray(a));
27 System.out.println("==========================");
28 int[] b = insertionSort(a, SORT_DES);
29 System.out.println("==========================");
30 System.out.println("排序结果：" + printAnArray(b));
31 }
32
33 /**
34 * 生成一个给定长度的整形数组
35 * @param length 数组长度
36 * @return
37 */
38 public static int[] createRandomArray(int length) {
39 if (length > 0) {
40 int[] a = new int[length];
41 for (int i = 0; i < length; i++) {
42 //产生随机数
43 Random random = new Random();
44 a[i] = random.nextInt(length * 50);
45 }
46 return a;
47 } else {
48 throw new NullPointerException("要创建的数组长度应该大于0");
49 }
50 }
51
52 /**
53 * 对数组a进行插入排序
54 *
55 * @param a
56 * 需要进行插入排序的数组
57 * @param desc
58 * 排序方式，其中<code>SORT_DES = 0</code>表示升序排列，
59 * <code>SORT_DESC = 1</code>表示降序排列
60 * @return 排序好的数组
61 */
62 public static int[] insertionSort(int[] a, int desc) {
63 if (a == null) {
64 return null;
65 }
66 if (desc == SORT_DES) {
67 for (int j = 1; j < a.length; j++) {
68 int temp = a[j];
69 int i = j;
70 int n = 1;
71 //新插入进来的数与之前的数逐个进行比较，直到找到插入位置
72 while ((i > 0) && (a[i - 1] > temp)) {
73 a[i] = a[i - 1];
74 i = i - 1;
75 System.out.println(" [" + j+"-"+n + "]次排序后结果为：" + printAnArray(a));
76 n = n + 1;
77 }
78 a[i] = temp;
79 n = 1;
80 System.out.println("第[" + j + "]次排序后结果为：" + printAnArray(a));
81 }
82 } else {
83 for (int j = 1; j < a.length; j++) {
84 int temp = a[j];
85 int i = j;
86 int n = 1;
87 while ((i > 0) && (a[i - 1] < temp)) {
88 a[i] = a[i - 1];
89 i = i - 1;
90 System.out.println(" [" + j+"-"+n + "]次排序后结果为：" + printAnArray(a));
91 n = n + 1;
92 }
93 a[i] = temp;
94 n = 1;
95 System.out.println("第[" + j + "]次排序后结果为：" + printAnArray(a));
96 }
97 }
98 return a;
99 }
100
101 /**
102 * 打印数组信息
103 *
104 * @param a
105 */
106 public static StringBuffer printAnArray(int[] a) {
107 if (a == null) {
108 return null;
109 }
110 StringBuffer buffer = new StringBuffer();
111 for (int j = 0; j < a.length; j++) {
112 buffer.append(" " + a[j] + " ");
113 }
114 return buffer;
115 }
116 }运行效果：
升序排列要进行插入排序的数组为： 184 177 95 28 13 14
==========================
[1-1]次排序后结果为： 184 184 95 28 13 14
第[1]次排序后结果为： 177 184 95 28 13 14
[2-1]次排序后结果为： 177 184 184 28 13 14
[2-2]次排序后结果为： 177 177 184 28 13 14
第[2]次排序后结果为： 95 177 184 28 13 14
[3-1]次排序后结果为： 95 177 184 184 13 14
[3-2]次排序后结果为： 95 177 177 184 13 14
[3-3]次排序后结果为： 95 95 177 184 13 14
第[3]次排序后结果为： 28 95 177 184 13 14
[4-1]次排序后结果为： 28 95 177 184 184 14
[4-2]次排序后结果为： 28 95 177 177 184 14
[4-3]次排序后结果为： 28 95 95 177 184 14
[4-4]次排序后结果为： 28 28 95 177 184 14
第[4]次排序后结果为： 13 28 95 177 184 14
[5-1]次排序后结果为： 13 28 95 177 184 184
[5-2]次排序后结果为： 13 28 95 177 177 184
[5-3]次排序后结果为： 13 28 95 95 177 184
[5-4]次排序后结果为： 13 28 28 95 177 184
第[5]次排序后结果为： 13 14 28 95 177 184
==========================
排序结果： 13 14 28 95 177 184 降序排列要进行插入排序的数组为： 43 133 132 27 280 46
==========================
[1-1]次排序后结果为： 43 43 132 27 280 46
第[1]次排序后结果为： 133 43 132 27 280 46
[2-1]次排序后结果为： 133 43 43 27 280 46
第[2]次排序后结果为： 133 132 43 27 280 46
第[3]次排序后结果为： 133 132 43 27 280 46
[4-1]次排序后结果为： 133 132 43 27 27 46
[4-2]次排序后结果为： 133 132 43 43 27 46
[4-3]次排序后结果为： 133 132 132 43 27 46
[4-4]次排序后结果为： 133 133 132 43 27 46
第[4]次排序后结果为： 280 133 132 43 27 46
[5-1]次排序后结果为： 280 133 132 43 27 27
[5-2]次排序后结果为： 280 133 132 43 43 27
第[5]次排序后结果为： 280 133 132 46 43 27
==========================
排序结果： 280 133 132 46 43 27 下面代码增加了日志功能：
1 /**
2 *
3 */
4 package com.b510.algorithms;
5
6 import java.io.File;
7 import java.io.FileWriter;
8 import java.util.Random;
9
10 /**
11 * 插入排序算法
12 * @author hongten(hongtenzone@foxmail.com)<br>
13 * @date 2013-6-7
14 */
15 public class PartTwoAlgorithms {
16
17 /**
18 * 降序排列
19 */
20 public static final int SORT_DESC = 1;
21 /**
22 * 升序排列
23 */
24 public static final int SORT_DES = 0;
25 /**
26 * 日志文件名称
27 */
28 public static final String LOG_FILE_NAME = "hongtenLog.txt";
29
30 public static StringBuffer buffer = new StringBuffer();
31
32 public static void main(String[] args) {
33 int[] a = createRandomArray(15);
34 System.out.println("要进行插入排序的数组为：" + printAnArray(a));
35 setContent("要进行插入排序的数组为：" + printAnArray(a));
36 System.out.println("==========================");
37 setContent("==========================");
38 int[] b = insertionSort(a, SORT_DESC);
39 System.out.println("==========================");
40 setContent("==========================");
41 System.out.println("排序结果：" + printAnArray(b));
42 setContent("排序结果：" + printAnArray(b));
43 writeToFile(buffer.toString());
44 }
45
46 public static void setContent(String str){
47 buffer.append(str + "\n");
48 }
49
50 /**
51 * 写入输出到日志文件中
52 * @param str
53 */
54 public static void writeToFile(String str){
55 File file = new File(LOG_FILE_NAME);
56 try {
57 FileWriter fw = new FileWriter(file);
58 fw.write(str + "\n");
59 fw.flush();
60 } catch (Exception e) {
61 e.printStackTrace();
62 }
63 }
64
65 /**
66 * 生成一个给定长度的整形数组
67 * @param length 数组长度
68 * @return
69 */
70 public static int[] createRandomArray(int length) {
71 if (length > 0) {
72 int[] a = new int[length];
73 for (int i = 0; i < length; i++) {
74 //产生随机数
75 Random random = new Random();
76 a[i] = random.nextInt(length * 50);
77 }
78 return a;
79 } else {
80 throw new NullPointerException("要创建的数组长度应该大于0");
81 }
82 }
83
84 /**
85 * 对数组a进行插入排序
86 *
87 * @param a
88 * 需要进行插入排序的数组
89 * @param desc
90 * 排序方式，其中<code>SORT_DES = 0</code>表示升序排列，
91 * <code>SORT_DESC = 1</code>表示降序排列
92 * @return 排序好的数组
93 */
94 public static int[] insertionSort(int[] a, int desc) {
95 if (a == null) {
96 return null;
97 }
98 if (desc == SORT_DES) {
99 for (int j = 1; j < a.length; j++) {
100 int temp = a[j];
101 int i = j;
102 int n = 1;
103 //新插入进来的数与之前的数逐个进行比较，直到找到插入位置
104 while ((i > 0) && (a[i - 1] > temp)) {
105 a[i] = a[i - 1];
106 i = i - 1;
107 System.out.println(" [" + j+"-"+n + "]次排序后结果为：" + printAnArray(a));
108 setContent(" [" + j+"-"+n + "]次排序后结果为：" + printAnArray(a));
109 n = n + 1;
110 }
111 a[i] = temp;
112 n = 1;
113 System.out.println("第[" + j + "]次排序后结果为：" + printAnArray(a));
114 setContent("第[" + j + "]次排序后结果为：" + printAnArray(a));
115 }
116 } else {
117 for (int j = 1; j < a.length; j++) {
118 int temp = a[j];
119 int i = j;
120 int n = 1;
121 while ((i > 0) && (a[i - 1] < temp)) {
122 a[i] = a[i - 1];
123 i = i - 1;
124 System.out.println(" [" + j+"-"+n + "]次排序后结果为：" + printAnArray(a));
125 setContent(" [" + j+"-"+n + "]次排序后结果为：" + printAnArray(a));
126 n = n + 1;
127 }
128 a[i] = temp;
129 n = 1;
130 System.out.println("第[" + j + "]次排序后结果为：" + printAnArray(a));
131 setContent("第[" + j + "]次排序后结果为：" + printAnArray(a));
132 }
133 }
134 return a;
135 }
136
137 /**
138 * 打印数组信息
139 *
140 * @param a
141 */
142 public static StringBuffer printAnArray(int[] a) {
143 if (a == null) {
144 return null;
145 }
146 StringBuffer buffer = new StringBuffer();
147 for (int j = 0; j < a.length; j++) {
148 buffer.append(" " + a[j] + " ");
149 }
150 return buffer;
151 }
152 }运行效果：
要进行插入排序的数组为： 537 424 33 491 507 481 355 208 565 404 530 463 234 335 354
==========================
第[1]次排序后结果为： 537 424 33 491 507 481 355 208 565 404 530 463 234 335 354
第[2]次排序后结果为： 537 424 33 491 507 481 355 208 565 404 530 463 234 335 354
[3-1]次排序后结果为： 537 424 33 33 507 481 355 208 565 404 530 463 234 335 354
[3-2]次排序后结果为： 537 424 424 33 507 481 355 208 565 404 530 463 234 335 354
第[3]次排序后结果为： 537 491 424 33 507 481 355 208 565 404 530 463 234 335 354
[4-1]次排序后结果为： 537 491 424 33 33 481 355 208 565 404 530 463 234 335 354
[4-2]次排序后结果为： 537 491 424 424 33 481 355 208 565 404 530 463 234 335 354
[4-3]次排序后结果为： 537 491 491 424 33 481 355 208 565 404 530 463 234 335 354
第[4]次排序后结果为： 537 507 491 424 33 481 355 208 565 404 530 463 234 335 354
[5-1]次排序后结果为： 537 507 491 424 33 33 355 208 565 404 530 463 234 335 354
[5-2]次排序后结果为： 537 507 491 424 424 33 355 208 565 404 530 463 234 335 354
第[5]次排序后结果为： 537 507 491 481 424 33 355 208 565 404 530 463 234 335 354
[6-1]次排序后结果为： 537 507 491 481 424 33 33 208 565 404 530 463 234 335 354
第[6]次排序后结果为： 537 507 491 481 424 355 33 208 565 404 530 463 234 335 354
[7-1]次排序后结果为： 537 507 491 481 424 355 33 33 565 404 530 463 234 335 354
第[7]次排序后结果为： 537 507 491 481 424 355 208 33 565 404 530 463 234 335 354
[8-1]次排序后结果为： 537 507 491 481 424 355 208 33 33 404 530 463 234 335 354
[8-2]次排序后结果为： 537 507 491 481 424 355 208 208 33 404 530 463 234 335 354
[8-3]次排序后结果为： 537 507 491 481 424 355 355 208 33 404 530 463 234 335 354
[8-4]次排序后结果为： 537 507 491 481 424 424 355 208 33 404 530 463 234 335 354
[8-5]次排序后结果为： 537 507 491 481 481 424 355 208 33 404 530 463 234 335 354
[8-6]次排序后结果为： 537 507 491 491 481 424 355 208 33 404 530 463 234 335 354
[8-7]次排序后结果为： 537 507 507 491 481 424 355 208 33 404 530 463 234 335 354
[8-8]次排序后结果为： 537 537 507 491 481 424 355 208 33 404 530 463 234 335 354
第[8]次排序后结果为： 565 537 507 491 481 424 355 208 33 404 530 463 234 335 354
[9-1]次排序后结果为： 565 537 507 491 481 424 355 208 33 33 530 463 234 335 354
[9-2]次排序后结果为： 565 537 507 491 481 424 355 208 208 33 530 463 234 335 354
[9-3]次排序后结果为： 565 537 507 491 481 424 355 355 208 33 530 463 234 335 354
第[9]次排序后结果为： 565 537 507 491 481 424 404 355 208 33 530 463 234 335 354
[10-1]次排序后结果为： 565 537 507 491 481 424 404 355 208 33 33 463 234 335 354
[10-2]次排序后结果为： 565 537 507 491 481 424 404 355 208 208 33 463 234 335 354
[10-3]次排序后结果为： 565 537 507 491 481 424 404 355 355 208 33 463 234 335 354
[10-4]次排序后结果为： 565 537 507 491 481 424 404 404 355 208 33 463 234 335 354
[10-5]次排序后结果为： 565 537 507 491 481 424 424 404 355 208 33 463 234 335 354
[10-6]次排序后结果为： 565 537 507 491 481 481 424 404 355 208 33 463 234 335 354
[10-7]次排序后结果为： 565 537 507 491 491 481 424 404 355 208 33 463 234 335 354
[10-8]次排序后结果为： 565 537 507 507 491 481 424 404 355 208 33 463 234 335 354
第[10]次排序后结果为： 565 537 530 507 491 481 424 404 355 208 33 463 234 335 354
[11-1]次排序后结果为： 565 537 530 507 491 481 424 404 355 208 33 33 234 335 354
[11-2]次排序后结果为： 565 537 530 507 491 481 424 404 355 208 208 33 234 335 354
[11-3]次排序后结果为： 565 537 530 507 491 481 424 404 355 355 208 33 234 335 354
[11-4]次排序后结果为： 565 537 530 507 491 481 424 404 404 355 208 33 234 335 354
[11-5]次排序后结果为： 565 537 530 507 491 481 424 424 404 355 208 33 234 335 354
第[11]次排序后结果为： 565 537 530 507 491 481 463 424 404 355 208 33 234 335 354
[12-1]次排序后结果为： 565 537 530 507 491 481 463 424 404 355 208 33 33 335 354
[12-2]次排序后结果为： 565 537 530 507 491 481 463 424 404 355 208 208 33 335 354
第[12]次排序后结果为： 565 537 530 507 491 481 463 424 404 355 234 208 33 335 354
[13-1]次排序后结果为： 565 537 530 507 491 481 463 424 404 355 234 208 33 33 354
[13-2]次排序后结果为： 565 537 530 507 491 481 463 424 404 355 234 208 208 33 354
[13-3]次排序后结果为： 565 537 530 507 491 481 463 424 404 355 234 234 208 33 354
第[13]次排序后结果为： 565 537 530 507 491 481 463 424 404 355 335 234 208 33 354
[14-1]次排序后结果为： 565 537 530 507 491 481 463 424 404 355 335 234 208 33 33
[14-2]次排序后结果为： 565 537 530 507 491 481 463 424 404 355 335 234 208 208 33
[14-3]次排序后结果为： 565 537 530 507 491 481 463 424 404 355 335 234 234 208 33
[14-4]次排序后结果为： 565 537 530 507 491 481 463 424 404 355 335 335 234 208 33
第[14]次排序后结果为： 565 537 530 507 491 481 463 424 404 355 354 335 234 208 33
==========================
排序结果： 565 537 530 507 491 481 463 424 404 355 354 335 234 208 33 这样我们也可以在日志文件中查看。这种是针对控制台显示不完的情况下的一种解决方案。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2013-06-07 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读