如何在Java中为shellsort排序正确实现Knuth序列？

Question

有没有人能提供一个简单的使用Knuth序列的Java外壳排序的工作示例？我在互联网上找了好几个地方，但都找不到一个适合我的解释。我在概念层面上理解外壳排序-因为它是一种插入排序，它是在一个随着时间的推移而缩小的间隔上完成的，直到达到1的间隔-这实际上是一种插入排序。然而，Knuth序列是(k *3- 1)/2，并且前几个间隙的列表通常表示为1，4，13，40,121。诸若此类。

我的问题是，这将如何实现？起始间隔实际上是1，还是这个序列在它大于正在排序的列表的大小之前生成的值？如果差距从1开始，如果我对shell排序的理解是正确的，那么目的就会失效。有没有人能解释一下这个？我觉得我错过了一些对理解这件事至关重要的东西。

提前谢谢。

Answer 1

延迟回答，但对于任何未来的旁观者太懒而不愿关注其他答案的链接，或者如果链接断开……

这是一种实现Knuth算法的方法，以按降序查找初始间隙值和剩余间隙值：

// Find initial gap.
gap = 1; 
while gap < arrayLength {
  gap = gap * 3 + 1;
}

// Perform the main sorting logic...

// Somewhere within code, at the end
// of the main sorting logic, find next
// descending gap value.
gap /= 3;

起始间隔不是1。它是在遍历要排序的数组的长度之前计算的最后一个最高数字。

底部的除以3部分基本上与while循环中执行的计算顺序相反，以便以降序获得序列中的下一个间隔值。这是每次在主排序逻辑结束时完成的。

另外，公式实际上是(3^k - 1) / 2，而不是(3k - 1) /2。前者将产生正确的序列(1，4，13，40，...)而后者是不正确的。

Answer 2

我在http://algs4.cs.princeton.edu/上找到了一个(参见“基本排序”一章)。源代码可以在here上找到

Shellsort类提供了使用

和Knuth的递增序列(1，4，13，40，...)对数组进行排序的静态方法。有关其他文档，请参阅Robert Sedgewick和Kevin Wayne的“算法，第四版”的"http://algs4.cs.princeton.edu/21elementary“(第2.1节)。