插入排序法
插入排序是除冒泡排序外比较出名的数组排序方法,和冒泡排序一样,用来解决数组内元素按照由大到小(或者由小到大)的问题的----当然,首先这个数组内的元素首先可以被比较.
第一步我们应该知道"插入排序"的思想是什么样子的:
首先我们要有一个数组,我们要把这个数组内的元素从小到大排列.
假设这里有一个名为num的int数组:
23 20 12 45 10
插入排序的第一步是从前两个元素开始的:
- 首先把 20 从数组中临时"拿出来"(要注意是从数组的第二个数开始我们的操作的),用 20 和 23 比较,很显然 20<23 ,这个时候就需要把 23 往后挪一位,再把 20 放到 23 的位置去.
第一步结束.现在的数组状态是:
20 23 12 45 10
这个时候我们已经确定了前两位是从小到大排列的了.下面要向第三个数下手了!想象我们就是计算机里排列这个数组的脑袋一根筋的家伙:
- 我们现在拿到第三个数 12 了.这个时候我们先把 12 从数组中临时"拿出来",让它和它前面的那一位----23比较, 12 < 23 ,不幸的 23 要往后挪一位,挪到刚才12在的位置.然后,12 去和 20 比较,可怜的 20 也要往后挪一位,挪到刚才 23 所在的位置. 12这个数再往前一看,前面就是头了,没有其他数字了,所以它就安心坐在了刚才 20 所在的"数组第一个位置"去了.
现在数组的状态是什么呢?
12 20 23 45 10
很不错!我们已经迈出了两步了,可是下面遇到了刚才我们没遇到的情况
- 数组的第四个数是 45 ,我们作为上帝,知道它大于前面的任何一个数.计算机怎么判断呢? 首先它拿到 45 这个数,让它和它前面的"伙计"比一下, 45 >23 ,OK!再往前就不用比了!为什么?因为经过上一步的处理, 45 这个数之前的肯定是从小到大排列的啦!如果 45 这个数比 前面那些数中最大的还要大,那 45 肯定是"迄今为止"我们遇到的最大的数了!
45 的问题解决了,还剩最后一个数字 10. 想必我已经不用多说了!
代码应该怎么写呢
无论我们思想多么666,如果写不出来代码还是白搭.
最简单的是整个程序的框架,里面定义我们想要的数组:
public class Array {
public static void main(String[] args) {
int[] array = {23,20,12,45,10};
}
}
这个算法中我们从数组的第二个数开始操作,一直到最后一个,很显然此处应该有一个循环,我们用最常见的for循环:
public class Array {
public static void main(String[] args) {
int[] array = {23,20,12,45,10};
for(int i = 1; i < array.length; i++){
}
}
}
循环里干什么呢?首先应该把我们每次拿到的"主角"(第一轮是20,第二轮是12...)放到一个临时的位置,如果需要挪位置,让它前面的家伙直接占用自己的位置就行了,自己不会消失.等找到合适的位置后再从这个"临时位置"坐到应该坐的地方去.
public class Array {
public static void main(String[] args) {
int[] array = {23,20,12,45,10};
for(int i = 1; i < array.length; i++){
int temp = array[i];
}
}
}
然后呢?我们要判断"主角"和前面那些家伙的关系了,而且我们会从最近的位置一直往前走,一直找到一个比自己小的,然后就落脚了,很显然,我们接下来不但有""判断",还有"循环"----用来保持"主角"一直向前的脚步:
public class Array {
public static void main(String[] args) {
int[] array = {23,20,12,45,10};
for(int i = 1; i < array.length; i++){
int temp = array[i];
for(int j = i - 1; j >= 0; j--){
if(temp < array[j]){
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = temp;
}
}
}
看上面的if判断中,只要遇到了比"主角"小的数,立刻就停止向前的脚步!然后停在当前位置(注意!因为for循环每次结束之前都会做" j -- "这个语句,所以"当前位置"是" j + 1 "的地方.换句话说," j + 1"就是为了补偿每次for语句结束后的" j -- "运算).
这个时候我们发现:第二个的for语句里面紧接着就是一个判断,我们为什么不直接把这个判断放到这个for内部的判断里面呢?这样一来我们又发现这下连break都省了,因为如果for内部判断不通过的话直接就跳出for循环了有木有!
如果你以为尘埃落定了的话你就打错算盘了!当我们把这段代码做好了,发现运行时竟然会报错!难道方法有问题吗?不不不!难道你没有发现j变量定义的位置有不足之处吗?j变量是个局部变量!我们竟然在for循环外使用了它!改吧!我们直接把i和j都定义到外面去好了!
public class Array {
public static void main(String[] args) {
int[] array = {23,20,12,45,10};
int i, j;
for(i = 1; i < array.length; i++){
int temp = array[i];
for(j = i - 1; j >= 0 && temp < array[j]; j--){
array[j + 1] = array[j];
}
array[j + 1] = temp;
}
}
}
好了,运行看看这段代码能不能达到我们的目的!!
