希尔排序 希尔排序( Shell's method)又称“缩小增量排序”( Diminishing Increment Sort), 是由 D.L. Shel在1959年提出来的。它的作法是:先取定一个小于n的整数d1作为第 个增量,把文件的全部记录分成d1个组,所有距离为d1的倍数的记录放在同 个组中,在各组内进行直接插入排序;然后,到第二个增量d2<d1重复上述分组和 排序,直至所取的增量d=1(d<d-1<.<d2d1),即所有记录放在同一组中进行 直接插入排序为止。 先从一个具体的例子来看希尔排序。假设待排序文件有10个记录,其关键字分别是 49,38,65,97,76,13,27,49,55,04。增量序列取值依次为:5,3,1 第一趟排序时,d1=5,整个文件被分成5组:(R1,R),(R2,R7),…,(Rs, R10)各组中的第1个记录都自成一个有序区,我们依次将各组的第2个记录R6, R,R10分别插入到各组的有序区中,使文件的各组均是有序的,其结果见图9- 2的第七 第二趟排序时,d2=3,整个文件分成三组:(R1,R4,R,R10),(R2,R3,Rs (R3,R6,R),各组的第1个记录仍自成一个有序区,然后依次将各组的第2个 记录R4,R,R6分别插入到该组的当前有序区中,使得(R1,R4),(R2,R5), (R3,R6)均变为新的有序区,接着依次将各组的第3个记录R7,R8,R9分别插 入到该组当前的有序区中,又使得(R1,R4R7),(R2,R5,Rg),(R3,R6, R)均变为新的有序区,最后将R10插入到有序区(R1,R4,R-)中就得到第 趟排序结果。 最后一趟排序时,d3=1,即是对整个文件做直接插入排序,其结果即为有序文件希尔排序 希尔排序（Shell’s Method）又称“缩小增量排序”（Diminishing Increment Sort）， 是由D.L.Shell在1959年提出来的。它的作法是：先取定一个小于n的整数d1作为第 一个增量，把文件的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一 个组中，在各组内进行直接插入排序；然后，到第二个增量d2<d1重复上述分组和 排序，直至所取的增量dt=1（dt<dt -1<…<d2<d1），即所有记录放在同一组中进行 直接插入排序为止。 先从一个具体的例子来看希尔排序。假设待排序文件有10个记录，其关键字分别是： 49，38，65，97，76，13，27，49/，55，04。增量序列取值依次为：5，3，1。 第一趟排序时，d1=5，整个文件被分成5组：（R1，R6），（R2，R7），…，（R5， R10）各组中的第1个记录都自成一个有序区，我们依次将各组的第2个记录R6， R7，…R10分别插入到各组的有序区中，使文件的各组均是有序的，其结果见图9- 2的第七行。 第二趟排序时，d2=3，整个文件分成三组：（R1，R4，R7，R10），（R2，R5，R8）， （R3，R6，R9），各组的第1个记录仍自成一个有序区，然后依次将各组的第2个 记录R4，R5，R6分别插入到该组的当前有序区中，使得（R1，R4），（R2，R5）， （R3，R6）均变为新的有序区，接着依次将各组的第3个记录R7，R8，R9分别插 入到该组当前的有序区中，又使得（R1，R4，R7），（R2，R5，R8），（R3，R6， R9）均变为新的有序区，最后将R10插入到有序区（R1，R4，R7）中就得到第二 趟排序结果。 最后一趟排序时，d3=1，即是对整个文件做直接插入排序，其结果即为有序文件