※ 这是一个稍微有些难度的挑战题。如果各位觉得太难可以暂时跳过,等具备一定实力后再回过头来挑战。

enter image description here enter image description here


答案不正确时的注意点

■ 是否在最后执行了g = 1 的普通插入排序,以保证数列顺序正确


讲解

我们之前提到过,插入排序法可以高速处理顺序较整齐的数据,而希尔排序法就是充分发挥插入排序法这一特长的高速算法。希尔排序法中,程序会重复进行以间隔为g 的元素为对象的插入排序。举个例子,设g 的集合为G,对A={4, 8, 9, 1, 10, 6, 2, 5, 3, 7} 进行G={4, 3, 1}的希尔排序,其整体过程如图3.9 所示。

图3.9 中,我们按照处理顺序自上而下地列出了数组元素的变化。每一步计算中,程序都将A[i](最后一个深灰色元素)插入前方间隔为g 的元素列(此时已经排序完毕)的恰当位置。图右侧的补充说明,是为了 标出各组间隔为g 的插入排序。这里请注意,程序的处理顺序与组的顺序无关。

要想完成数据排序必须在最后执行g=1,即普通的插入排序法。不过,此时对象数据的顺序应该已经很整齐了。

enter image description here

考察

g=enter image description here 的选择方法数不胜数,至今为止人们已对其进行了许多研究,不过其相关解析超出了本书的范围,所以这里仅给各位举个例子:当g=1, 4, 13, 40, 121…,即enter image description here=3enter image description here+1 时,算法的复杂度基本维持在O(enter image description here)。除上述数列外,只要使用最终值为1 的递减数列,基本都能高效地完成数据排序。不过,如果遇到2 的幂指数(enter image description here=1, 2, 4, 8…)等g=1 之前几乎不需要排序的数列,希尔排序法的效率会大打折扣。

参考答案

enter image description here enter image description here

评论

本文目前还没有评论……

我要评论

需要登录后才能发言
登录未成功,请修改提交。