java 算法之插入排序算法

浏览数：23 / 时间：2015年06月08日

这算是经典算法了，网上很多朋友都写了，有的我看不懂，所以我自己按照我自己所理解的写出来，

我觉得只有自己写出来的东西才是自己的

主要思路：

1.将数组的前两个数进行大小排序

2.将第三个数与前两个数进行比较，将第三个数插入到合适的位置

3.循环

其实这样来将对于新手来说，将其变成代码是有点困难的。

我也是。我很笨，没办法，只有将详细的一步一步写出来

// 数组【3，5，1，2，8，9】

如有这样一个数组，按照上面的思路，我们从第二个数开始，就是5，5要跟3比较，第二个位置就是5要插入的位置

【3，5，1，2，8，9】

再1，1跟5比较，1比5要小，所以，要将5的位置和1的位置的数值进行调换，也就是数值移位。

【3，1，5，2，8，9】

继续跟前一个比较，再次移位

【1，3，5，2，8，9】

此时的位置是我们要插入的位置

依次规律，得到排序结果为如下所示。

【1，2，3，5，8，9】

主要代码如下：

public void sort(int a[]){

        int length=a.length; //数组长度
       int j;               //当前值的位置对于初始而言，就是5所对应的位置
       int i;               //指向j前的位置   对于初始而言，就是3所对应的位置
       int key;           //当前要进行插入排序的值    对于初始而言，就是5
       //从数组的第二个位置开始遍历插入，也就是说跟数组的第一个值做比较，如果比第一个的小就将第一个的值往后移
       for(j=1;j<length;j++){
           key=a[j]; //第一次是将5的值赋给key，而后一次类推
           i=j-1;     //第一次是3对应的位置
           //a[i]比当前值大时，a[i]后移一位,空出i的位置，好让下一次循环的值后移
           while(i>=0 && key < a[i]){// 第一次是 5比3大，不执行循环
               a[i+1]=a[i]; //将a[i]值后移
               i--;         //i前移
           }//跳出循环(找到要插入的中间位置或已遍历到0下标)
           a[i+1]=key;    //将当前值插入，也就是3对应位置的后一个位置，也就是5的位置，最后的结果就是，将5这个位置重新指向了5，结果没什么影响而已
       }
       }