算法概述
簡(jiǎn)單地說(shuō)，插入排序就是將待排序列中未排序的元素插入到前面已經(jīng)排序好的子序列當(dāng)中的過(guò)程，直到最后一個(gè)元素萌抵。
舉個(gè)例子编整，對(duì)數(shù)組{9,3,7,2,66,22}進(jìn)行插入排序的過(guò)程可以分為以下幾步：
1舔稀，我們將當(dāng)前的有序子序列稱(chēng)為A，初始時(shí)A只有一個(gè)元素 9
2掌测，從A后面開(kāi)始内贮，將元素插入到A中合適的位置，使A仍然有序汞斧，同時(shí)A的大小加1
3夜郁，重復(fù)步驟2，直到最后一個(gè)元素
步驟2插入的過(guò)程：
因?yàn)锳已經(jīng)有序粘勒，所以將某個(gè)元素e插入A竞端，只要從A的末尾開(kāi)始掃描，假設(shè)當(dāng)前掃描到的元素為f庙睡，如果e比f(wàn)小事富，就將f后移一位（相當(dāng)于將e的位置騰出來(lái)了），如果e不比f(wàn)小乘陪，則此次掃描完成统台，最后將e放在最后掃描終止的位置上。
下面的圖片較為形象地表達(dá)了插入排序的過(guò)程：
實(shí)現(xiàn)代碼 (Java)
public void insertSort(int[] input) {
int i, j, tmp;
for (i = 1; i < input.length; i++) {
tmp = input[i];
for (j = i; j > 0 && tmp < input[j - 1]; j--) {
input[j] = input[j - 1];
}
input[j] = tmp;
}
}
復(fù)雜度
插入排序存在最好情況和最壞情況啡邑。最好情況就是贱勃，序列已經(jīng)有序了，在這種情況下谤逼，需要進(jìn)行的比較操作為 (n-1)次贵扰，最壞的情況是序列是反序的，此時(shí)需要進(jìn)行的比較操作為n*(n-1)/2次流部，插入排序的平均時(shí)間復(fù)雜度為O(n2)拔鹰。由于不需要額外的空間，插入排序的空間復(fù)雜度為O(1)贵涵。
適用場(chǎng)景
插入排序不適合數(shù)據(jù)量比較大的排序應(yīng)用列肢。但是，如果需要排序的數(shù)據(jù)量很小宾茂，或者若已知輸入元素大致上按照順序排列瓷马，那么插入排序還是一個(gè)不錯(cuò)的選擇。
