插入排序就是每一步都將一個待排數(shù)據(jù)按其大小插入到已經(jīng)排序的數(shù)據(jù)中的適當位置，直到全部插入完畢。 插入排序方法分直接插入排序和折半插入排序兩種。

詳細代碼請參考Algorithm。參考代碼比文字好理解。

時間復雜度與空間復雜度

時間復雜度：O（n^2)
空間復雜度：O（1）

最少比較次數(shù)：（已排序的數(shù)組）n-1次
最多比較次數(shù)：（降序的數(shù)組）n(n-1)/2次

數(shù)組在已排序或者是“近似排序”時，插入排序效率的最好情況運行時間為O(n)；插入排序最壞情況運行時間和平均情況運行時間都為O（n^2) 。

插入排序不適合對大量數(shù)據(jù)排序，適合對接近排序的數(shù)據(jù)排序。插入排序是穩(wěn)定排序。通常，插入排序呈現(xiàn)出二次排序算法中的最佳性能。對于具有較少元素（如n<=15）的列表來說，二次算法十分有效。在列表已被排序時，插入排序是線性算法O(n)。在列表“近似排序”時，插入排序仍然是線性算法。在列表的許多元素已位于正確的位置上時，就會出現(xiàn)“近似排序”的條件。

算法描述

假定n是數(shù)組的長度，首先假設第一個元素被放置在正確的位置上，這樣僅需從1到n-1范圍內(nèi)對剩余元素進行排序。對于每次遍歷，從0到i-1范圍內(nèi)的元素已經(jīng)被排好序，每次遍歷的任務是：通過掃描前面已排序的子列表，將位置i處的元素定位到從0到i的子列表之內(nèi)的正確的位置上。

將arr[i]復制為一個名為target的臨時元素。向下掃描列表，比較這個目標值target與arr[i-1]、arr[i-2]的大小，依次類推。這個比較過程在小于或等于目標值的第一個元素(arr[j])處停止，或者在列表開始處停止（j=0）。在arr[i]小于前面任何已排序元素時，后一個條件（j=0）為真，因此，這個元素會占用新排序子列表的第一個位置。在掃描期間，大于目標值target的每個元素都會向右滑動一個位置（arr[j]=arr[j-1]）。一旦確定了正確位置j，目標值target（即原始的arr[i]）就會被復制到這個位置。與選擇排序不同的是，插入排序將數(shù)據(jù)向右滑動，并且不會執(zhí)行交換。