一，插入排序介紹

?插入排序是基于比較的排序。所謂的基于比較，就是通過比較數(shù)組中的元素，看誰大誰小，根據(jù)結(jié)果來調(diào)整元素的位置。

因此，對于這類排序，就有兩種基本的操作：①比較操作； ②交換操作

其中，對于交換操作，可以優(yōu)化成移動操作，即不直接進(jìn)行兩個(gè)元素的交換，還是用一個(gè)樞軸元素(tmp)將當(dāng)前元素先保存起來，然后執(zhí)行移動操作，待確定了最終位置后，再將當(dāng)前元素放入合適的位置。（下面的插入排序就用到了這個(gè)技巧）--因?yàn)?，交換操作需要三次賦值，而移動操作只需要一次賦值！

有些排序算法，比較次數(shù)比較多，而移動次數(shù)比較少，而有些則相反。比如，歸并排序和快速排序，前者移動次數(shù)比較多，而后者比較次數(shù)比較多。

這里主要介紹插入排序

二，插入排序算法分析

插入排序算法有種遞歸的思想在里面，它由N-1趟排序組成。初始時(shí)，只考慮數(shù)組下標(biāo)0處的元素，只有一個(gè)元素，顯然是有序的。

然后第一趟 對下標(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]上的元素有序，也就是整個(gè)數(shù)組有序了。

它的遞歸思想就體現(xiàn)在：當(dāng)對位置 i 處的元素進(jìn)行排序時(shí)，[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

三，插入排序算法實(shí)現(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;

}