希尔排序 希尔排序( Shells method)又称“缩小增量排序”( Diminishing Increment sort), 是由 D.L. Shell在1959年提出来的。它的作法是:先取定一个小于n的整数d1作为第 个增量,把文件的全部记录分成d1个组,所有距离为d1的倍数的记录放在同 个组中,在各组内进行直接插入排序;然后,到第二个增量d2<d1重复上述分组和 排序,直至所取的增量d=1(d<d-1<.<d2<d1),即所有记录放在同一组中进行 直接插入排序为止 先从一个具体的例子来看希尔排序。假设待排序文件有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,R4,R (R,R5,R),(R3,R 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，即是对整个文件做直接插入排序，其结果即为有序文件
若不设置监视哨,根据上例的分析不难写出希尔排序算 法,请读者自行完成之。下面我们先分析如何设置监 视哨,然后给出具体算法。设某一趟希尔排序的增量 为h,则整个文件被分成h组:(R1,RH1,R2h+1,…), (R2,R1+2,R2h+2, (Rh, RL, R 因为各组中记录之间的距离均为是h,故第1组至第h组 的哨兵位置依次为1-h,2-h,…,0。如果象直接插入 排序算法那样,将待插入记录R:(h1≤iN)在查找插 入位置之前保存到监视哨中,那么必须先计Ri属于哪 组,才能决定使用哪个监视哨来保存Ri。为了避免 这种计算,我们可以将Ri保存到另一个辅肋记录X中, 而将所有监视哨R1,R2h,…,R0的关键字,设置为 小于文件中的任何关键字即可。因为增量是变化的, 所以,各趟排序中所需的监视哨数目也不相同,但是 我们可以按最大增量d1来设置监视哨
若不设置监视哨，根据上例的分析不难写出希尔排序算 法，请读者自行完成之。下面我们先分析如何设置监 视哨，然后给出具体算法。设某一趟希尔排序的增量 为h，则整个文件被分成h组：（R1，Rh+1，R2h+1，…）， （R2，Rh+2，R2h+2，…），…（Rh，R2h，R3h，…）， 因为各组中记录之间的距离均为是h，故第1组至第h组 的哨兵位置依次为1-h，2-h，…，0。如果象直接插入 排序算法那样，将待插入记录Ri（h+1≤i≤N） 在查找插 入位置之前保存到监视哨中，那么必须先计Ri属于哪 一组，才能决定使用哪个监视哨来保存Ri。为了避免 这种计算，我们可以将Ri保存到另一个辅肋记录X中， 而将所有监视哨R1-h，R2-h，…，R0的关键字，设置为 小于文件中的任何关键字即可。因为增量是变化的， 所以，各趟排序中所需的监视哨数目也不相同，但是 我们可以按最大增量d1来设置监视哨
rectype r[n+d /*Rd1-]为d1个监视哨 int dt /*dO到dt]为增量序列* SHELLSORT(R, d) Rectype r: int d[: fint i,j,k,h ectype temp int maxint=32767 /*机器中最大整数* for(F0; K<d[0]: 1++) RI.key=-maxint /*设置哨兵* K=0: H=d[k]: *取本趟增量* For(Fh+di: K<n+dl: i++) /*Rhd到Rn+dl-1插入当前有序区* /保存待插入记录R[]*/ whie(temp.key<Rkey)/*查找正确的插入位置* R[+h]R[i]} 后移记录* J *得到前一记录位置* RIh=temp; /插入R[*/ /*本趟排序完成* k++; i while (h! =1) /*增量为1排序后终止算法* /*SHELLSORT*/
rectype R[n+d1]； /* R[d1 -1]为d1个监视哨*/ int d[t]； /* d[0]到d[t-1]为增量序列*/ SHELLSORT(R,d) Rectype R[ ]； int d[ ]； {int i，j，k，h； rectype temp; int maxint=32767； /*机器中最大整数*/ for (i=0；i<d[0]；i++) R[i].key=-maxint； /*设置哨兵*/ K=0； Do{ H=d[k]； /*取本趟增量*/ For(i=h+di；i<n+d1；i++) /*R[h+d1]到R[n+d1-1]插入当前有序区*/ {temp=R[i]}； /*保存待插入记录R[i]*/ j=i-h； while(temp.key<R[j].key) /*查找正确的插入位置*/ {R[j+h]=R[j]}； /*后移记录*/ j=j-h； /*得到前一记录位置*/ } R[j+h]=temp； /*插入R[i]*/ } /*本趟排序完成*/ k++； } while (h！=1)； /*增量为1排序后终止算法*/ } /*SHELLSORT*/
读者可能看出,当增量h=1时, SHELLSORT算法与 INSERTSORT基 本一致 对希尔排序的分析提出了许多困难的数学问题,特别是如何选择增 量序列才能产生最好的排序效果,至今没有得到解决。希尔本为 最初提出取d1=n/2,d1=-d21,d,=1,t=山og2。后来又 有人提出其它选择增量序列的方法,如d+1=(dl)/3,d=1, t=og3n1;以及d1=-d1)2-,d=1,t=山og2n-1。 为什么希尔排序的时间性能优于直接插入排序呢?我们知道直接插 入排序在文件初态为正序时所需要时间最少,实际上,当文件初 基本有序时直接插入排序所需的比较和移动次数均较少。另一面, 当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间 复杂度On)和最坏时间复杂度On2)差别不大。在希尔排序时增量 较大,分组较多,每组的记录数目少,故各组内直接插入较快 后来增量d逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐 增多,但由于已经按d1作为距离排过序,使文件较近于有序状态, 所以新的国趟排序过程也较快。因此,希尔排序在较率上较直接 接入排序有较大的改进 希尔排序是不稳定的。参见图9-2的例子,该例中两个相同关键字49 在排序前后的相对次序发生了变化
读者可能看出，当增量h=1时，SHELLSORT算法与INSERTSORT基 本一致。 对希尔排序的分析提出了许多困难的数学问题，特别是如何选择增 量序列才能产生最好的排序效果，至今没有得到解决。希尔本为 最初提出取d1=┗n/2┛ ，di+1=┗di/2 ┛ ，dt=1，t=┗log2 n┛。后来又 有人提出其它选择增量序列的方法，如di+1=┗(di-1)/3┛，dt=1， t=┗log3n-1┛；以及di+1=┗(di-1 )/2┛ ，dt=1，t=┗log2 n -1┛。 为什么希尔排序的时间性能优于直接插入排序呢？我们知道直接插 入排序在文件初态为正序时所需要时间最少，实际上，当文件初 基本有序时直接插入排序所需的比较和移动次数均较少。另一面， 当n值较小时，n和n 2的差别也较小，即直接插入排序的最好时间 复杂度O(n)和最坏时间复杂度O(n2 )差别不大。在希尔排序时增量 较大，分组较多，每组的记录数目少，故各组内直接插入较快， 后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐 增多，但由于已经按di-1作为距离排过序，使文件较近于有序状态， 所以新的国趟排序过程也较快。因此，希尔排序在较率上较直接 接入排序有较大的改进。 希尔排序是不稳定的。参见图9-2的例子，该例中两个相同关键字49 在排序前后的相对次序发生了变化
选择排序 选择排序( selection sort)也是一种简单排序法。一个记录最多只需进行 次交换就可以直接到达它的排序位置。 设待排序的文件为(R1,R2,…,Rn),进行选择排序的基本步骤如下: (1)置i为1 (2)当in时,重复下列步骤; 1)当(Ri,…,Rn)中选出一个关键字最小的记录Rmin,若Rmin不是R,即 Amini则交换Ri和Rmin的位置;否则,不进行交换。 2)i的值加1。 第1遍扫描时,在n个记录中为了选出最小关键字的记录,需要进行n-1次比 较,第2扫描时,在余下的n-1记录中,再选出具有最小关键字的记录需 要比较n-2次,…第n-1扫描时,在最后的2个记录中,比较1次选出最小 关键字的记录
选择排序 选择排序（selection sort）也是一种简单排序法。一个记录最多只需进行一 次交换就可以直接到达它的排序位置。 设待排序的文件为（R1，R2，…，Rn），进行选择排序的基本步骤如下： （1）置i 为1； （2）当i<n时，重复下列步骤； 1）当(Ri，…，Rn)中选出一个关键字最小的记录Rmin，若Rmin不是Ri，即 Rmin≠i则交换Ri和Rmin的位置；否则，不进行交换。 2）i的值加1。 第1遍扫描时，在n个记录中为了选出最小关键字的记录，需要进行n-1次比 较，第2扫描时，在余下的n-1记录中，再选出具有最小关键字的记录需 要比较n-2次，……第n-1扫描时，在最后的2个记录中，比较1次选出最小 关键字的记录