扫码获取更多资源

●希尔排序

希尔排序(Shell Sort)又称缩小增量排序，是对直接插入排序的改进。在直接插入排序 中，如果待排序记录按关键字基本有序，则其效率很高；如果待排序记录个数较少，则其效 率也很高。希尔排序正是从这两点分析出发对直接插入排序进行了改进，其基本思想是： 先将整个待排序记录序列分割成若干个子序列，在子序列内分别进行直接插入排序，待整个 序列基本有序时，再对全体记录进行一次直接插入排序。

希尔排序发明于1959年，它的名称源于它的发明者Donald Shell ,该算法是突破二次 时间屏障()(子)的第一批算法之一。

希尔排序需要解决两个关键问题：一是应该如何分割待排序记录，才能保证整个序列 逐步向基本有序发展；二是子序列内如何进行直接插入排序。

分割待排序记录

子序列的构成不能是简单地“逐段分割”，而是将相距某个“增量”的记录组成一个子序 列.这样才能有效地保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不 是局部有序。接下来的问题是增量应该如何取？到目前为止尚未有人求得一个最好的增量 序列。希尔(D. L. shell)最早提出的方法是：山=|_n/2」,&+1 =|_出/2丄且没有除1之外的公 因子，并且最后一个增量必须等于10开始时增量的取值较大，每个子序列中的记录个数较 少，并且提供了记录跳跃移动的可能，排序效率较高；后来增量逐步缩小，每个子序列中的 记录个数增加，但已基本有序，效率也较高。

注意：基本有序和局部有序不同。基本有序是指已接近正序，例如｛1, 2, 8, 4, 5, 6, 7, 3, 9｝；而局部有序只是某些部分有序，例如｛6, 7, 8, 9, 1, 2, 3, 4, 5｝,而局部有序不 能提高直接插入排序算法的时间性能。

算法描述

算法分析

希尔排序实质上是一种分组插入排序，每组插入与一趟直接插入排序相比，做了两处修 改：一是前后记录位置的增量为dk,而不为1;二是L.r[0]只作为暂存单元，而不作为“哨 兵，，，当jV = 0时，插入位置已经找到。

联系我们：