插入排序（insertion sort）介紹

插入排序是什麼

一個簡單的排序法，將數列分成已排序與未排序區，逐步將未排序區的元素插入前方已排序區的適當位置來完成排序。適合小數列（數列長度為10~1000）或已接近排好數列（判斷數列有無序）

舉例

有一組數列[5, 2, 4, 6, 1, 3]做插入排序。

1. 5視為已排好，未排序數列為[ 2, 4, 6, 1, 3]，所以我們可以得到一個數列[5 | 2, 4, 6, 1, 3]，其中 | 用來區隔已排序與未排序區。

2. 比較2,5，2比5小排在5前面，得[2,5 |4, 6, 1, 3]。

3. 比較4,5，4比5小排在5前面，得[2,4,5 |6, 1, 3]。

4. 比較4,2，4不比2小，它所在的就是正確位置，得[2,4,5 |6, 1, 3]。

5. 比較6,5，6不比5小，它所在的就是正確位置，得[2,4,5,6 | 1, 3]

6. 比較1,6，1比6小排在6前面，得[2,4,5,1,6 | 3]，1逐步比較直到找到適當位置，最後 [1,2,4,5, 6 |3]。

7. 比較3,6，3比6小排在6前面，得[1,2,4,5,3,6 | ]，3逐步比較直到找到適當位置，最後 [1,2,3,4,5, 6 |]。

8. 最後已排序數列為[1,2,3,4,5, 6 ]。

平均時間複雜度

數列由前往後掃須做n次，每個元素需掃描前面已排好的數列找出適當位置，須做n次，故時間複雜度為O(n^2)平方函數時間複雜度。

最佳時間複雜度（已排好）：O(n)

最差時間複雜度（逆序）：O(n^2)

平均時間複雜度：O(n^2)