梳状排序被证明是正确的吗?可以吗?

Question

我一直在对梳理排序进行一些研究，我试图弄清楚该算法是否已被证明是正确的。但是，我似乎找不到有关该算法的大量文档。不过，这是一个非常简单的算法 - 基本上是Bubble Sort的变体 - 我猜证明并不复杂。有没有人对我在哪里可以找到更多信息有想法，或者关于如何从头开始证明它的想法？

对于那些不熟悉Comb Sort的人，您可以在维基百科文章中找到伪代码。

Answer 1

让我们使用维基百科中的伪代码：

function combsort(array input) is
gap := input.size
shrink := 1.3
sorted := false
loop while sorted = false
gap := floor(gap / shrink)
if gap ≤ 1 then
gap := 1
sorted := true
end if
i := 0
loop while i + gap < input.size
if input[i] > input[i+gap] then
swap(input[i], input[i+gap])
sorted := false
end if
i := i + 1
end loop
end loop
end function

主循环是while sorted = false的，并且没有break语句提前停止循环，这对证明很有帮助：如果这个循环终止，那一定是sorted = true的情况。所以实际上，我们只需要展示两件事：首先，循环确实终止了，其次，如果sorted = true在循环的末尾，那么数组实际上是排序的。

• 循环终止是因为每次在迭代结束时sorted仍false时，要么gap变小，要么gap保持不变，数组中的反转次数变小。反演gap和反演数都是分别以 1 和 0 为界的整数，因此它们不能无限期地变小。
  • 如果gap是 2 个或更多，那么它在迭代中会变小(请注意floor函数)。
  • 如果gap为 1，则它保持在 1，并且sorted设置为在内部循环之前true。sorted只能通过将input[i]和input[i+1]交换为某些iinput[i] > input[i+1]来设置false。这样的交换将数组中的反转次数减少 1。内部循环在任何其他情况下都不执行交换，因此任何交换都不会在gap = 1时增加反转次数。
• 如果sorted = true在循环结束时，我们知道gap = 1因为否则sorted无法设置为true.然后我们也知道每个input[i] <= input[i+1]因为如果这对某些i不是真的，那么sorted就会被设置为false。因此，只有在数组中每对相邻元素都按顺序排列时，sorted才在循环结束时为真，即数组被排序。