希尔排序的详解

希尔排序的详解

希尔排序基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

举例说明：

对于这样一个无序的数组5 9 3 2 6 11 8 1 7 4 10 ，想把它变成顺序递增的数组1 2 3 4 5 6 7 8 9 10 11。先隔3个元素取一次：把5 2 8 4取了出来，往后搓一位，把9 6 1 10取出来，再往后搓一位，又把3 11 7取出来。分别对这三个小组排序成为递增的序列，再插回去，如图：

于是得到了第一趟排序的结果：2 1 3 4 6 7 5 9 11 8 10.现在再以2为间隔重复以上步骤（这次得到的是两个小组）得到了2 1 3 4 5 7 6 8 11 9 10。最后再以1为间隔再搞一次（实际上这一步就是从左到右两两比较，调整位置），就得到了想要的结果。

这就是希尔排序，其要义就是先进行宏观调整，再进行微观调整。