在大多數(shù)情況下扭吁，插入排序算法是基本的排序算法中最好的一種球碉，在一般情況下蜓斧，它比冒泡排序快一倍，比選擇排序還要快一點(diǎn)睁冬，它經(jīng)常被用到較復(fù)雜的排序算法的最后階段挎春，例如快速排序。
用插入排序?yàn)榛@球隊(duì)員排序
開始插入排序之前豆拨，把籃球隊(duì)員隨機(jī)順序排成一排直奋，從排序過程的中間開始，可以更好的理解插入排序施禾，這時(shí)隊(duì)列已經(jīng)排好了一半脚线。
局部有序
此時(shí)，在隊(duì)伍的中間有一個(gè)作為標(biāo)記的隊(duì)員弥搞，可以把一件紅色的毛巾扔到這個(gè)隊(duì)員前面邮绿，在這個(gè)作為標(biāo)記的隊(duì)員左邊的所有隊(duì)員已經(jīng)是局部有序的了渠旁，這就意味著這一部分人之間是按照順序排列的；每個(gè)人比他左邊的人都高船逮，然而這些隊(duì)員在隊(duì)列中最終的位置還沒有確定一死，因?yàn)楫?dāng)沒有被排過序的隊(duì)員要插入到他們中間的時(shí)候，他們的位置還要發(fā)生變動(dòng)傻唾。注意投慈，局部有序在冒泡排序和選擇排序中是不會(huì)出現(xiàn)的，在這兩個(gè)算法中冠骄，一組數(shù)據(jù)項(xiàng)在某個(gè)時(shí)刻是完全有序的伪煤；在插入排序中，一組數(shù)據(jù)僅僅是局部有序的凛辣。
被標(biāo)記的隊(duì)員
作為標(biāo)記的隊(duì)員抱既，稱為“被標(biāo)記”的隊(duì)員，他和他右邊所有的隊(duì)員都是未排過序的扁誓，下面將要做的是在局部有序組中的適當(dāng)位置插入被標(biāo)記的隊(duì)員防泵。然而要做到這一點(diǎn)，需要把部分已排序的隊(duì)員右移來騰出空間蝗敢。為了提供移動(dòng)所需的空間捷泞，就先讓被標(biāo)記的隊(duì)員出列(在程序中，把這個(gè)數(shù)據(jù)項(xiàng)存儲(chǔ)在一個(gè)臨時(shí)變量中)
現(xiàn)在移動(dòng)已經(jīng)排過序的隊(duì)員來騰出空間寿谴。將局部有序中最高的隊(duì)員移動(dòng)到原來被標(biāo)記隊(duì)員所在的位置锁右，次高的隊(duì)員移動(dòng)到原來最高的隊(duì)員所在的位置，依次類推
這個(gè)移動(dòng)過程什么時(shí)候結(jié)束呢讶泰？假設(shè)你和被標(biāo)記的隊(duì)員一起向隊(duì)列的左端移動(dòng)咏瑟，在每個(gè)位置上，隊(duì)員都向右移動(dòng)一位痪署，同時(shí)被標(biāo)記的隊(duì)員和下一個(gè)要移動(dòng)的隊(duì)員比較身高码泞。當(dāng)把最后一個(gè)比被標(biāo)記的隊(duì)員還高的隊(duì)員移位之后，這個(gè)移動(dòng)的過程就停止了狼犯，最后一次移位空出的位置余寥，就是被標(biāo)記隊(duì)員應(yīng)該插入的位置
現(xiàn)在，局部有序的部分里多了一個(gè)隊(duì)員辜王，而未排序的部分里少了一個(gè)隊(duì)員劈狐。作為標(biāo)記的毛巾向右移動(dòng)一個(gè)位置，所以它仍然放在未排序部分的最左邊的隊(duì)員面前呐馆。重復(fù)這個(gè)過程肥缔，直到所有為排序的隊(duì)員都被插入（插入排序由此得名）到局部有序隊(duì)列中合適的位置
public void insertionSort(){
int in,out;
for(out=1;out<nElems;out++){
long temp=a[out];
in=out;
while(in>0 && a[in-1]>temp){
a[in]=a[in-1];
--in;
}
a[in]=temp;
}
}
在外層的for循環(huán)中，out變量從1開始汹来，向右移動(dòng)续膳。他標(biāo)記了未排序部分的最左端的數(shù)據(jù)改艇，而在內(nèi)層的while循環(huán)中，in變量從out變量開始坟岔，向左移動(dòng)谒兄，直到temp變量小于in所致的數(shù)組數(shù)據(jù)項(xiàng)，或者它已經(jīng)不能再往做移動(dòng)為止社付。while循環(huán)的每一趟都向右移動(dòng)了一個(gè)已排序的數(shù)據(jù)項(xiàng)
插入排序中的不變性
在每趟結(jié)束時(shí)承疲，在將temp為止的項(xiàng)插入后，比outer變量下標(biāo)號(hào)小的數(shù)據(jù)項(xiàng)都是局部有序的
插入排序的效率
復(fù)制的次數(shù)大致等于比較的次數(shù)鸥咖。然而燕鸽，一次復(fù)制與一次交換的時(shí)間耗費(fèi)不同油宜，所以相對(duì)于隨機(jī)數(shù)據(jù)菜皂，這個(gè)算法比冒泡排序快一倍，比選擇排序略好乘凸，在任意情況下鸥拧，對(duì)于隨機(jī)順序的數(shù)據(jù)進(jìn)行插入排序也需要O(N2)的時(shí)間級(jí)党远。
對(duì)于已經(jīng)有序或者基本有序的數(shù)據(jù)來說，插入排序要好得多富弦，然而對(duì)于逆序排列的數(shù)據(jù)沟娱，每次比較和移動(dòng)都會(huì)執(zhí)行，所以插入排序不比冒泡排序快
幾種簡單排序之間的比較
- 一般情況下幾乎不太使用冒泡排序算法舆声，只有當(dāng)數(shù)據(jù)量很小的時(shí)候它有些應(yīng)用價(jià)值
- 選擇排序雖然把交換次數(shù)降到最低花沉，但比較的次數(shù)仍然很大柳爽，當(dāng)數(shù)據(jù)量很小媳握，并且交換數(shù)據(jù)相對(duì)于比較數(shù)據(jù)更加耗時(shí)的情況下，可以使用選擇排序
- 在大多數(shù)情況下磷脯，假設(shè)當(dāng)數(shù)據(jù)量比較小或基本上有序時(shí)蛾找，插入排序算法是三種簡單排序算法中最好的選擇，對(duì)于更大數(shù)據(jù)的排序來說赵誓，快速排序通常是最快的方法
