插入排序法

插入排序法（insertion sort algorithm）的概念

是逐一從未排序的原始資料中取出元素，再從已排序數列由前往後找到適當的位置插入，如果遇到大於自己的元素就插入此元素之前；否則插入在已排序數列的最後一項。

插入排序法規則(遞增)

① 將最前端的數當作「已排序」，把數值分為「已排序」和「未排序」兩部分。

② 將「未排序的第1個數」，由後往前逐一和「已排序」的數值比較，並插入到適當的位置。

③ 重複②，直到完成排序。

我們可以從以上的流程，歸納出實作的步驟：

1. 先從未排序的原始資料中，取出第 1 個元素加到已排序數列中的第一項。

2. 接著從未排序的原始資料中逐一取出元素。

3. 由前往後和已排序數列元素比較，遇到大於自己的元素就插入此元素之前；否則插入在已排序數列的最後一項。

4. 重複第 2、3 點的步驟，直到原始資料全部處理完成。