希尔排序是计算机专业考研中的一个重要知识点。希尔(Donald Shell)于1959年提出了这种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。以下是文都考研网小编为同学们整理的希尔排序相关复习资料,供大家参考学习。

【完整代码】

计算机专业考研

【技巧】

子序列的构成不是简单地“逐段分割” 将相隔某个增量dk的记录组成一个子序列让增量dk逐趟缩短(例如依次取5,3,1)直到dk=1为止。

【练习题目】

希尔排序的组内排序采用的是( )

A.直接插入排序B.折半插入排序C.快速排序D.归并排序

【参考答案】A

【考查知识点】希尔排序基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。

小编提醒同学们,在复习时,尤其要关注直接插入排序与希尔排序的区别。直接插入排序是稳定的;而希尔排序是不稳定的。直接插入排序更适合于原始记录基本有序的集合。希尔排序的比较次数和移动次数都要比直接插入排序少,当N越大时,效果越明显。在希尔排序中,增量序列gap的取法必须满足:最后一个步长必须是 1。直接插入排序也适用于链式存储结构;希尔排序不适用于链式结构。这些容易搞混的不同点,大家可以一一列举出来,重点理解记忆。更多计算机专业考研复习资料免费下载,请查询文都考研网。