algorithm - "A g-sorted array remains g-sorted even after h-sorting it"的含义是什么？

Question

当我看到上面的语句时，我正在阅读 shell-sorting。这意味着什么？它对我看待 shell 排序的方式有何不同？

PS:我不是在寻找声明的证据。

Answer 1

好吧，你可能暗示下一个排序阶段不会“搞砸”前面的步骤:如果你对数组进行 g 排序然后执行 h 排序，结果数组仍然是 g 排序的，所以它是应用 h 排序“没有错”。由于插入排序(shellsort 基于它)对于几乎有序的数组来说很快，你可以争辩说 h-sorting 做了一些积极的事情(如果它改变了一些事情)并且没有造成伤害，而且代价不大。所以它总是一个进步:它要么是接近线性的，要么在排序方面取得了一些进步。

显然，选择步长值的问题对于 shellsort 来说是一个独立且非常重要的问题。