如何在Java中正确实现希尔排序的Knuth序列？

Question

请提供一个使用Knuth序列的Java希尔排序的简单工作示例。我在互联网上查找了几个地方，但找不到适合我的解释。我理解希尔排序的概念——它是一种插入排序，通过缩小隙距来进行排序，直到达到1的隙距，然后就变成了插入排序。然而，Knuth序列是(k * 3 - 1)/2，并且前几个间隙的列表通常表示为[1, 4, 13, 40, 121..等等]。

我的问题是如何实现这一点？起始间隔实际上是1吗？还是在生成的值大于正在排序的列表大小之前的值？如果间隔从1开始，那么如果我正确地理解了希尔排序，目的将被击败。能否有人解释一下这个问题？我觉得我错过了理解这件事情的关键。

提前致谢。

- Dielan

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、...），而后者则是错误的。

- Sal_Vader_808

Answer 2

我在这里找到了一个（请参阅“Elementary Sorts”章节）。源代码可以在这里找到。

Shell类提供了使用Knuth增量序列（1、4、13、40等）的Shellsort对数组进行排序的静态方法。有关详细文档，请参见Robert Sedgewick和Kevin Wayne的《算法，第四版》中的“http://algs4.cs.princeton.edu/21elementary”（第2.1节）。

- Sergey Chepurnov

---

这个代码示例基本上是我需要看到的。然而，这里的第2.1节实际上没有解释为什么此处的代码将gap变量初始化为Knuth序列中最后一个小于排序集合大小三分之一的数字：// 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ... int h = 1; while (h < N/3) h = 3*h + 1; 您能否解释一下原因？ - Dielan

@Dielan 我可以建议你找到R.Sedgewick解释它是如何工作的视频（约10分钟）。使用短语“shellsort sedgewick princeton”搜索该视频。 - Sergey Chepurnov