|
最近这段时间比较忙，几乎都忘了写博客这件事情，今天周末下着小雨，坐在桌前不知该干啥，就想起了把之前写的东西继续写下去。废话不多说，今天给大家介绍一下插入排序，直接进入主题。 插入排序思想：从第二个位置开始插入，依次与该数据之前所有数据进行比较，数据比该数据大，数据往后顺移。否则该数据插入到第一个比该数据小的数据后面。 是不是比较绕口，比较难理解？解释一下：“该数据”指的要插入的数据。下面通过图与文字来说明插入排序的思想。 同样以5个数据为例。数据为：8、5 、2 、6 、1。由于排序思想中涉及到顺移，数组顺移会覆盖数据，因此需要一个变量记录“该数据”。
第一次比较过程： 从第二位置开始插入：第二个位置的数据为5，5也就是“该数据”。 依次与该数据之前所有数据进行比较：5是第二个位置数据，也就是说5要与第一个位置上的数据进行比较。 数据比该数据大，往后顺移：数据指的是8,8比5大。8往后顺移，即8移到第二个位置。那么5也就排在第一个位置。
第二次比较过程： 第一次已经从第二位置插入了，这次就从第三个位置开始插入：第三个位置的数据为2，“该数据”指的也就是2。 2要与第二、第一位置上的数据依次比较。很明显，第二、第一位置上的数据都比2大。8和5数据都要往后顺移。比较后的数据顺序是2、5、8。
第三次比较过程： 这次从第四个位置开始插入，第四个位置数据为6，“该数据”指的也就是6。 6要与第三、第二、第一位置上的数据比较。6与第三个位置数据8比较，8往后顺移到底四个位置。6与第二个位置数据5比较，5比6要小，6就插入到第一个比6小的数据 5 的后面。至此第三次比较结束。
第四次比较过程： 这次比较从第五个位置开始插入，第五个数据为1，“该数据”指的也就是1。 1要与第四、第三、第二、第一位置上的数据进行比较。由于1在这组数据中是最小数据，因此第四、第三、第二、第一位置上的数据都往后顺移一位。1则插入到第一个位置上。
到这里整个数据的插入过程已经分析完。 我们可以看出，该数据只要找到插入位置，就不会在与插入位置之前的数据比较。因为插入数据之前的数据都比该数据小。也就是说，找到插入位置后，插入位置之前的数据已经是有序的了。 整个过程我们已经清晰明了，下面就需要对插入排序思想转换成我们的代码。 [Java] 纯文本查看 复制代码 public static void main(String[] args) {
// 定义10个数据的数组
int data[] = new int[10];
// 初始化数组
initData(data);
// 打印排序前数组数据
print(data);
// 插入排序
insertSort(data);
// 打印排序后的数组数据
print(data);
}
/**
* 插入排序：从第二个位置开始插入，依次与该数据之前所有数据进行比较，数据比该数据大，数据往后顺移。否则该数据插入到第一个比该数据小的数据后面。
*
* @param data
*/
private static void insertSort(int[] data) {
// 定义一个变量用于记录该数据，因为数据数据顺移会覆盖数据。
int temp = 0;
// 比较次数
for (int i = 1; i < data.length; i++) {
// 该数据
temp = data[i];
//该for循环比较的是 找到第一个比该数据小的数据的位置。
int j = i - 1;
for (;j >= 0; j--) {
//判断数据与该数据大小
if (data[j] > temp) {
// 数据比该数据大，数据往后顺移
data[j + 1] = data[j];
} else {
// 找到了第一个比该数据小的数据的位置，j。跳出循环
break;
}
}
// break走到这里，找到了第一个比该数据小的数据的位置，j；插入位置就是 j+1.
//或者内for循环结束，找到了第一个比该数据小的数据的位置，j的值为-1；插入位置就是 j+1，也就是0的位置.
data[j + 1] = temp;
}
//==============================对上面代码进行改造后是注释下面这部分代码=================================
/*
*
* int temp = 0;
* for (int i = 1; i < data.length; i++) {
* // 该数据 temp = data[i];
*
* int j = i - 1;
* //该for循环比较的是 找到第一个比该数据小的数据的位置。
* while (j >= 0) {
*
* if (data[j] > temp) {
*
* // 数据往后顺移
* data[j + 1] = data[j];
*
* } else {
*
* // 找到了第一个比该数据小的数据的位置，j.
* break;
* }
*
* j--; }
*
* // 走到这里，找到了第一个比该数据小的数据的位置，j；插入位置就是 j+1.
*
* data[j + 1] = temp;
*
* }
*/
//=================================================================
}
// 该方法随机生成10个1-100的随机数
private static void initData(int[] data) {
for (int i = 0; i < data.length; i++) {
data[i] = (int) Math.ceil(Math.random() * 100);
}
}
// 该方法用于打印数组数据
private static void print(int[] data) {
System.out.print("[");
for (int i = 0; i < data.length; i++) {
if (i != data.length - 1) {
System.out.print(data[i] + ",");
} else {
System.out.println(data[i] + "]");
}
}
}
到这里插入排序详解完毕。 下一篇：递归思想与汉诺塔详解，敬请期待......
| 
收藏
淘帖
踩
