2. 插入排序—希尔排序（Shell Sort）

希尔排序是1959年由D.L.Shell提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序。

基本思想：

　　　　先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，在对全体记录依次进行直接插入排序。

操作方法：

　　　　1、选择一个增量序列t1,t2,....,tk,其中ti>tj,tk=1;

　　　　2、按增量序列的个数k,对序列进行k趟排序；

　　　　3、每趟排序，根据对应的增量ti，将带排序列分割成若干长度为m的子序列，分别对个子序列进行直接插入排序。仅增量因子为1时，整个序列为一个表来处理，表长度即为整个序列的长度。

希尔排序的示例：

算法实现：

排序算法（三）