一待秃，插入排序介紹
?插入排序是基于比較的排序骇窍。所謂的基于比較，就是通過比較數(shù)組中的元素锥余，看誰大誰小，根據(jù)結(jié)果來調(diào)整元素的位置痢掠。
因此驱犹，對于這類排序，就有兩種基本的操作：①比較操作足画； ②交換操作
其中雄驹，對于交換操作，可以優(yōu)化成移動操作淹辞，即不直接進(jìn)行兩個元素的交換医舆，還是用一個樞軸元素(tmp)將當(dāng)前元素先保存起來，然后執(zhí)行移動操作象缀，待確定了最終位置后蔬将，再將當(dāng)前元素放入合適的位置。（下面的插入排序就用到了這個技巧）--因為央星，交換操作需要三次賦值霞怀，而移動操作只需要一次賦值！
有些排序算法莉给，比較次數(shù)比較多毙石，而移動次數(shù)比較少，而有些則相反颓遏。比如徐矩，歸并排序和快速排序，前者移動次數(shù)比較多叁幢，而后者比較次數(shù)比較多滤灯。
這里主要介紹插入排序
二，插入排序算法分析
插入排序算法有種遞歸的思想在里面，它由N-1趟排序組成力喷。初始時刽漂，只考慮數(shù)組下標(biāo)0處的元素，只有一個元素弟孟，顯然是有序的贝咙。
然后第一趟 對下標(biāo) 1 處的元素進(jìn)行排序，保證數(shù)組[0,1]上的元素有序拂募；
第二趟 對下標(biāo) 2 處的元素進(jìn)行排序庭猩，保證數(shù)組[0,2]上的元素有序；
.....
.....
第N-1趟對下標(biāo) N-1 處的元素進(jìn)行排序陈症，保證數(shù)組[0,N-1]上的元素有序蔼水，也就是整個數(shù)組有序了。
它的遞歸思想就體現(xiàn)在：當(dāng)對位置 i 處的元素進(jìn)行排序時录肯，[0,i-1]上的元素一定是已經(jīng)有序的了趴腋。?? 排序前:????6????3????3????5????6????3????1????0????6????4
i?=?0:????6
i?=?1:????3????6
i?=?2:????3????3????6
i?=?3:????3????3????5????6
i?=?4:????3????3????5????6????6
i?=?5:????3????3????3????5????6????6
i?=?6:????1????3????3????3????5????6????6
i?=?7:????0????1????3????3????3????5????6????6
i?=?8:????0????1????3????3????3????5????6????6????6
i?=?9:????0????1????3????3????3????4????5????6????6????6
排序后:????0????1????3????3????3????4????5????6????6????6
三，插入排序算法實現(xiàn)
/**
*插入排序
*/
private? static? int[]?insertSort(int[]arr){
if(arr?==?null||?arr.length?<?2){
????return arr;
}
for(inti=1;i<arr.length;i++);
for(intj=i;j>0;j--){
???????????? ?? if(arr[j]<arr[j-1]){
??????????????? inttemp=arr[j];
????????????? ? arr[j]=arr[j-1];
??????????????? arr[j-1]=temp;
??????? }else{
??????????????? break;
}
}
}
return? arr;
}
