5

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

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

提前致谢。

4

2 回答 2

5

迟到的答案，但对于任何未来的旁观者都懒得关注其他答案的链接，或者链接中断......

这是一种实现 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, ...) 而后者不正确的一个。

于 2019-07-15T01:26:07.313 回答
2

我在http://algs4.cs.princeton.edu/找到了一个（参见“基本排序”一章）。源代码可以在这里找到

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

于 2015-10-26T06:59:58.570 回答