插入類排序法

在最壞情況下，簡單插入排序需要n 子序列的分割方法如下： 其效率與增量序列有關。

主要分為兩種：
① 簡單插入排序法；
基本思想：所謂插入排序，是指將無序序列中的各元素依次插入到已經有序的線性表中。
一般來說，假設線性中前j－1元素已經有序，現在要將線性表中第j個元素插入到前面的有序子表中，插入過程如下：
道德將第j個元素放到一個變數T中，然後從有序子表的最後一個元素（即線性表中第j－1個元素）開始，往前逐個與T進行比較，將大於T的元素均依次向後移動一個位置，直到發現一個元素不大於T為止，此時就將T（即原線性表中的第j個元素）插入到剛移出的空位置上，有序子表的長度就變為j了。效率與冒泡法相同
在最壞情況下，簡單插入排序需要n（n－1）/2次比較。
② 希爾排序法；
基本思想：將整個無序序列分割成若干小的子序列分別進行插入排序。
子序列的分割方法如下：
將相隔某個增量H的元素構成一個子序列。在排序過程中，逐次減小這個增量，最後當H減到1時，進行一次插入排序，排序就完成。增量序列一般取h=n/2k（k=1，2，…【log2n】，其中n為待排序序列的長度。
其效率與增量序列有關。 在最壞情況下，需要的比較次數為O（N^1.5）。