插入排序法

插入排序是除冒泡排序外比较出名的数组排序方法,和冒泡排序一样,用来解决数组内元素按照由大到小(或者由小到大)的问题的----当然,首先这个数组内的元素首先可以被比较.

---

第一步我们应该知道"插入排序"的思想是什么样子的:

首先我们要有一个数组,我们要把这个数组内的元素从小到大排列.
假设这里有一个名为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;
        }
    }
}

好了,运行看看这段代码能不能达到我们的目的!!