什么是插入排序：
如 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大，所以位置不動
最后結(jié)果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次賦值，影響效率?？梢宰兂梢淮钨x值，如：用變量保存第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的值賦給空余的位置。
最后結(jié)果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;
? ? }
}
對于相對有序數(shù)組，插入排序效率要高，時間復(fù)雜度為on2
