arrays - g-sorted-ness 不受后面的 h-sorting : is proof correct? 的影响

Question

假设:数组 A 是 g 排序的。 IE。对于所有整数 x 和特定整数 g，A[x] < A[x+g] < A[x+2g] ...

现在，如果我们在将它复制到数组 B 后进行 h 排序，以实现条件:对于另一个特定整数 h，B[x] < B[x+h] < B[x+2h] .. .

假设是在对它进行 h 排序后，对于任意整数 h 和 g，数组仍然保持 g 排序。

证明:如果与假设相反，h-sorting 会影响 g-sorted-ness，这将是由于 A[x1] > A[x1+h]，对于某些 x1 in g-sorted 数组 A，我们交换了 x 和 x+h 处的元素——这种交换最终破坏了 g-sortedness

现在，我们知道对于所有 x，A[x-g] < A[x] < A[x+g] < A[x+2g] 因为它已经是 g 排序的。

所以，A[x+h-g] < A[x+h] < A[x+h+g]

对于特定的 x=x1，我们有 A[x1] > A[x1+h] 因此我们需要交换 x1 和 x1+h 处的元素。在交换之前，数组的条件是:对于所有 x

{A[x-g] ; A[x+h-g]} < A[x+h] < A[x] < {A[x+g] ; A[x+h-g]}

其中 {} 符号表示我们不知道 {} 中元素的顺序，但 {} 中的每个元素分别满足排序条件。

对于一个特定的x=x1，即使我们交换x1+h和x1处的元素，交换前的条件也是

{A[x1-g] ; A[x1+h-g]} <A[x1+h] < A[x1] < {A[x1+g] ; A[x1+h-g]}

交换后是

黄金:{B[x1-g]； B[x1+h-g]} <B[x1] < B[x1+h] < {B[x1+g] ; B[x1+h-g]}

这可能会以两种方式破坏 g-sorted-ness:
1. B[x1] > B[x1-g]
2. B[x1+g] > B[x1]

但是上面标记为 GOLD 的交换条件显示，这两个销毁条件都不成立。因此，在对 g 排序的数组进行 h 排序后，g 排序特性不会被破坏。

问题:这是一个数学上有效的证明吗？请评论。

Answer 1

证明不好，因为假设是错误的。考虑以下 h 排序算法:

1. 将 g 排序数组的内容倒在地板上。
2. 稍微调整一下元素，然后去吃午饭。
3. 回来对元素进行 h 排序。

这会导致元素数组经过 h 排序但不再是 g 排序。好吧，我们真的应该证明，对于上述论点，存在一些不是 g 排序的 h 排序方法。这个例子很简单。令 g = 1 和 h = 2。取数组

A = 1 2 3 4

A 是 g 排序和 h 排序的。但是如果 h-sorted 而不是 g-sorted，则元素的以下排列:

B = 1 3 2 4

因此，不能保证 h 排序会产生 g 排序的列表。

现在有一些叫做稳定的排序算法；根据定义，如果 h 排序算法保留了您试图显示的属性，那么它就是 g 稳定的。不过，您需要证明特定 h 排序算法的 g 稳定属性，并且它适用于该算法，而不是一般的 h 排序。