c++ - C++中的shell排序序列实现

Question

我正在阅读 Robert Sedwick 的 Algorithms in C++ 中有关 shell 排序的内容。

这里更改增量的外循环导致了这个紧凑的 shellsort 实现，它使用增量序列 1 4 13 40 121 364 1093 3280 9841 。 . . .

template <class Item>
void shellsort(Item a[], int l, int r)
{
    int h;
    for (h = 1; h <= (r - l) / 9; h = 3 * h + 1);
    for (; h > 0; h = h / 3)
    {
        for (int i = l + h; i <= r; i++)
        {
            int j = i; Item v = a[i];
            while (j >= l + h && v < a[j - h])
            {
                a[j] = a[j - h]; j -= h;
            }
            a[j] = v;
        }
    }
}

我的问题是作者在什么基础上检查条件 h <= (r-l)/9，以及为什么作者要除以 9。

Answer 1

循环:

for (h = 1; h <= (r - l) / 9; h = 3 * h + 1);

计算h的初值.该值必须小于它将使用的范围:

h <= (r - l)

每当这种情况过去时，h更新为 3 * h + 1 ，这意味着即使 h小于 (r-l) ，更新后的值可能会更大。为了防止这种情况，我们可以检查 h 的下一个值是否会超过最大的索引:

(h * 3) + 1 <= (r - l)

这将确保 h小于数组的范围。

例如:假设我们有一个大小为 42 的数组，这意味着索引从 0 到 41。使用上述条件:

h = 1, is (3 * 1 + 1) <= (41 - 0) ? yes! -> update h to 4
h = 4, is (3 * 4 + 1) <= (41 - 0) ? yes! -> update h to 13
h = 13, is (3 * 13 + 1) <= (41 - 0) ? yes! -> update h to 40
h = 40, is (3 * 40 + 1) <= (41 - 0) ? no! => h will begin at 40

这意味着我们的初始 h是 40，因为 h仅略小于数组的范围，将完成很少的工作，算法将仅检查以下内容:

1. 数组[40]需要和数组[0]交换吗？
2. 数组[41]需要和数组[1]交换吗？

这个有点没用，第一次迭代只进行了两次检查。较小的初始值 h意味着更多的工作将在第一次迭代中完成。

使用:

h <= (r - l) / 9

确保h的初始值足够小以允许第一次迭代完成有用的工作。作为一个额外的优势，它看起来也比以前的情况更干净。

您可以将 9 替换为任何大于 3 的值。为什么大于 3？确保(h * 3) + 1 <= (r - l)仍然是真的!

但切记不要写首字母 h太小:Shell 排序基于插入排序，它只在小型或接近排序的数组上表现良好。就个人而言，我不会超过 h <= (r - l) / 15 .