读者可能看出,当增量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 在排序前后的相对次序发生了变化