插入排序（Insertion sort）是一種簡單直觀且穩定的排序算法。 <br> 如果有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入后此數據序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，算法適用于少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。 <br> 插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最后一個元素除外（讓數組多一個空間才有插入的位置），而第二部分就只包含這一個元素（即待插入元素）。在第一部分排序完成后，再將這個最后元素插入到已排好序的第一部分中。 <br> 插入排序的基本思想是：每步將一個待排序的記錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。 <br> ### 原理： 現有一組數組 arr = [5, 6, 3, 1, 8, 7, 2, 4] ``` [5] 6 3 1 8 7 2 4 ↑ │ └───┘ [5, 6] 3 1 8 7 2 4 ↑ │ └────────┘ [3, 5, 6] 1 8 7 2 4 ↑ │ └──────────┘ [1, 3, 5, 6] 8 7 2 4 ↑ │ └──┘ [1, 3, 5, 6, 8] 7 2 4 ↑ │ └────┘ [1, 3, 5, 6, 7, 8] 2 4 ↑ │ └────────────────┘ [1, 2, 3, 5, 6, 7, 8] 4 ↑ │ └─────────────┘ [1, 2, 3, 4, 5, 6, 7, 8] ``` ``` function insertSort($arr){ for($i=1; $i<count($arr); $i++){ $tmp = $arr[$i]; $key = $i-1; while($key >= 0 && $tmp < $arr[$key]){ $arr[$key+1] = $arr[$key]; $key--; } if (($key+1)!=$i) { $arr[$key+1]=$tmp; } } return $arr; } ```