### 基本原理
在要排序的一組數中，假設前面的數已經是排好順序的，現在要把第n個數插到前面的有序數中，使得這n個數也是排好順序的。如此反復循環，直到全部排好順序。
### 動畫演示
### 算法步驟
1. 從第一個元素開始，該元素可以認為已經被排序
2. 取出下一個元素，在已經排序的元素序列中從后向前掃描
3. 如果該元素（已排序大于新元素），將該元素移動到下一位置
4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到該位置后
6. 重復步驟2~5
### 代碼實現
```
function insertSort($arr)
{
$length = count($arr);
for ($i = 1;$i < $length; $i++) { // 遍歷數組
$iTemp = $arr[$i]; // 獲得當前值
$iPos = $i - 1; // 獲得當前值的前一個位置
// 如果當前值小于前一個值切未到數組開始位置
while (($iPos >= 0) && ($iTemp < $arr[$iPos])) {
$arr[$iPos + 1] = $arr[$iPos]; // 把前一個的值往后放一位
$iPos--; // 位置遞減
}
$arr[$iPos+1] = $iTemp;
}
return $arr;
}
// 調用測試
$arr = [3,1,13,5,7,11,2,4,14,9,150,6,12,10,8];
print_r(insertSort($arr));
```
### 平均時間復雜度：O(n2)
如果目標是把n個元素的序列升級排序，那么采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需（n-1）次即可。最壞的情況就是，序列是降序排列，那么此時需要進行的比較共有1/2 * n(n-1)次。插入排序的賦值操作是比較操作的次數加上(n-1)次。平均來說插入排序算法復雜度為O(n2)。因而，插入排序不適合對于數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小于千，那么插入排序還是一個不錯的選擇。插入排序在工業級庫中也有著廣泛的應用，在STL的sort算法和stdlib的qsort算法中，都將插入排序作為快速排序的補充，用于少量元素的排序。
### 小結
插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩定的。
