插入排序

什么是插入排序：

---

如 1 2 6 5 4

第1步：1不动

第2步：2比1大 2不动

第3步：6比2大 6不动

第4步：5比6小，交换5和6的位置，5比2大，5的位置不动

变成12564

第5步：4比6小，交换4和6的位置，5比4大，交换4和5的位置，4比2大，所以位置不动

最后结果12456

代码

public class sort {

public  static  void main(String args[])

{

int array[]={1,24,3424,2,4,1,242,556,34,23,5,13,4};

        array=paixu(array);

        for(int i=0;i

{

System.out.println(array[i]);

        }

}

public static int[]paixu(int [] array)

{

int exchange=0;

        for(int i=1;i

{

for(int j=i-1;j>=0&&array[j]>array[j+1];j--)

{

exchange=array[j+1];

                    array[j+1]=array[j];

                    array[j]=exchange;

            }

}

return  array;

    }

}

---

插入排序也有缺点就是其每次比较大小后都要进行交换，一次交换是3次赋值，影响效率。可以变成一次赋值，如：用变量保存第i个元素的值，如果前一个元素比后一个元素大，则前一个元素移到后一个元素位置，一直到小于为止，将变量的值赋给该位置元素，这样会大大提高效率

---

如 1 2 6 5 4

第1步：1不动

第2步：2比1大 2不动

第3步：6比2大 6不动

第4步：5比6小，用x保存5，将6赋值给5的位置，5比2大，将x的值赋值

变成12564

第5步：4比6小，用x保存4，将6的值赋给4的位置，5比4大，将5的值赋给6的位置，4比2大，所以将x的值赋给空余的位置。

最后结果12456

---

public class sort {

public  static  void main(String args[])

{

int array[]={1,24,3424,2,4,1,242,556,34,23,5,13,4};

        array=paixu(array);

        for(int i=0;i

{

System.out.println(array[i]);

        }

}

public static int[]paixu(int [] array)

{

int j;

        int exchange;

        for(int i=1;i

{

exchange=array[i];

            for (j=i;j>0 &&array[j-1]>exchange;j--)

{

array[j]=array[j-1];

            }

array[j]=exchange;

        }

return  array;

    }

}

对于相对有序数组，插入排序效率要高，时间复杂度为on2