把表分成兩部分，前半部分已排序，後半部分未排序，最壞情況需要n(n-1)/2次比較。
基本概念,實現,
基本概念
所謂插入排序，是指將無序序列中的各元素依次插入到已經有序的線性表中。
一般來說，假設線性中前j－1元素已經有序，現在要將線性表中第j個元素插入到前面的有序子表中，插入過程如下：
將第j個元素放到一個變數T中，然後從有序子表的最後一個元素（即線性表中第j－1個元素）開始，往前逐個與T進行比較，將大於T的元素均依次向後移動一個位置，直到發現一個元素不大於T為止，此時就將T（即原線性表中的第j個元素）插入到剛移出的空位置上，有序子表的長度就變為j了。效率與冒泡法相同
實現
套用舉例：用 |分開，假設初始為 5 | 1 7 3 1 6
一次插入排序，把第一個1插入前邊已排序部分，得
1 5 | 7 3 1 6
後邊依次是
1 5 7 | 3 1 6
1 3 5 7 | 1 6
1 1 3 5 7 | 6
1 1 3 5 6 7
一次插入排序，把第一個1插入前邊已排序部分，得
1 5 | 7 3 1 6
後邊依次是
1 5 7 | 3 1 6
1 3 5 7 | 1 6
1 1 3 5 7 | 6
1 1 3 5 6 7
