1

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

对于不熟悉 Comb Sort 的人，您可以在Wikipedia 文章中找到伪代码。

4

1 回答 1

0

让我们使用来自Wikipedia的伪代码：

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只能false通过交换input[i]和input[i+1]某些iwhere来设置input[i] > input[i+1]。这样的交换将数组中的反转次数减少了 1。内部循环在任何其他情况下都不执行交换，因此在 时没有交换可以增加反转次数gap = 1。
  • 如果sorted = true在循环结束时，我们知道gap = 1因为 elsesorted不能设置为true. 然后我们也知道 everyinput[i] <= input[i+1]因为如果这对某些人来说不是真的i，那么sorted就会被设置为false。因此，sorted只有在循环结束时数组中的每一对相邻元素都是有序的，即数组已排序时，才为真。
于 2020-01-23T01:39:34.590 回答