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

Question

有人可以提供一个使用 Knuth 序列的 Java shellsort 的简单工作示例吗？我在互联网上查看了几个地方，但找不到适合我的解释。我在概念层面上理解 shellsort - 因为它是一种插入排序，它是在间隙上完成的，间隙随着时间的推移而缩小，直到间隙达到 1 - 这本质上是一种插入排序。然而，Knuth 序列是 (k * 3 - 1)/2，前几个间隙的列表通常表示为 [1, 4, 13, 40, 121.. 等等]。

我的问题是如何实现？起始间隙实际上是 1，还是该序列在大于要排序的列表的大小之前生成的值？如果间隙从 1 开始，如果我正确理解希尔排序，目的就会落空。有人可以解释一下吗？我觉得我错过了一些对于理解这件事至关重要的东西。

提前致谢。

Answer 1

迟到的答案，但对于那些懒得关注其他答案的链接或链接断开的 future 旁观者......

这是一种实现 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 和 NOT (3k - 1)/2。前者将产生正确的序列 (1, 4, 13, 40, ...) 和后者是错误的。