algorithm - 关于shell排序算法

Question

我正在读一本关于算法的书。它在shell排序中提到如下

Shellsort 的一个重要属性（我们在没有证明的情况下声明）是一个 (h subscipt k) hk-sorted 文件，然后是 (h subsciprt (k-1)) hk-1-sorted 仍然是 hk-sorted。如果不是这种情况，该算法可能没有什么价值，因为早期阶段所做的工作将被后期阶段撤消。

我的问题是作者所说的上述陈述是什么意思？

谢谢！

Answer 1

Shell排序是一种多遍排序算法。它通过以特定整数“步幅”值对数组的子集进行排序来工作k，即仅访问kth数组中的每个元素。

最初使用较大的步幅值，在随后的传递中，该步幅值减小，直到最终传递以步幅运行1（通常只是标准插入排序阶段）并且数组完全排序。

您所询问的声明仅表示在较早的通道（较大的步幅值）上进行的任何排序都由以后的通道（较小的步幅值）保留。如果不是这种情况，那么 shell 排序使用的多遍方法将毫无意义。

希望这可以帮助。