什么是插入排序：
如 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
