希尔排序算简单实现与分析

1、根本思想
  先取一个小于n的整数d1作为第一个增量，把文件的全体记载分成d1个组。所有距离为d1的倍数的记载放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1反复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记载放在同一组中进行直接插入排序为止。该办法本质上是一种分组插入办法。   先取一个小于n的整数d1作为第一个增量，把文件的全体记载分成d1个组。所有距离为d