插入排序：
包括：直接插入排序，二分插入排序（又稱折半插入排序），鏈表插入排序，希爾排序（又稱縮小增量排序）
插入排序算法思路：
假定這個數組的序是排好的,然后從頭往后,如果有數比當前外層元素的值大,則將這個數的位置往后挪,直到當前外層元素的值大于或等于它前面的位置為止.這具算法在排完前k個數之后,可以保證a[1…k]是局部有序的,保證了插入過程的正確性.
上圖為：直接插入排序
一般來說，插入排序都采用in-place在數組上實現。具體算法描述如下：
1.
從第一個元素開始，該元素可以認為已經被排序
2. 取出下一個元素，在已經排序的元素序列中從后向前掃描
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置
4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到下一位置中
6. 重復步驟2
算法的時間復雜度：
如果目標是把n個元素的序列升序排列，那么采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。最壞情況就是，序列是降序排列，那么此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數加上
(n-1)次。平均來說插入排序算法的時間復雜度為O(n^2)。因而，插入排序不適合對于數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小于千，那么插入排序還是一個不錯的選擇。