0

冒泡排序算法（伪代码）：

Input: Array A[1...n]
for i <- n,...,2 do
    for j <- 2,...,i do
        if A[j - 1] >= A[j] then
            swap the values of A[j-1] and A[j];

我不确定，但我的证明似乎有效，但过于复杂。你能帮我清理一下吗？

循环不变：在每次迭代 i 之后，A 的 i - n + 1 个最大元素处于它们应该是 A 非降序排序的位置。在数组 A 包含多个最大值的情况下，令最大元素为所有可能最大值中索引最小的元素。

归纳法（i = n）：内部循环遍历 A 的每个元素。最终，j 指向最大的元素。这个值将被交换，直到它到达位置 i = n，这是数组 A 中的最高位置，因此是 A 中最大元素的最终位置。

归纳步骤：（i = m -> i = m - 1 for all m > 3）：内部循环遍历 A 的每个元素。最终，j 指向尚未排序的最大元素。这个值将被交换，直到它到达位置 i = m - 1，这是数组 A 中尚未排序的位置的最高位置，因此是 A 中最大的尚未排序元素的最终位置。

算法执行完毕后，位置1的剩余元素也处于其最终位置，因为如果不是，其右侧的元素将不会处于其最终位置，这是矛盾的。量子点

4

1 回答 1

3

我倾向于用以下术语重铸你的证明： Bubble sort A[1..n]: for i in n..2 for j in 2..i swap A[j - 1], A[j] if they are not already in order

循环不变量：让 P(i) <=> 对所有 k st i < k <= n。A[k] = 最大值（A[1..k]）

基本情况：最初 i = n 并且不变量 P(n) 很容易满足。

归纳步骤：假设某些 P(m + 1) 的不变量成立，表明在内循环执行后，P(m) 的不变量成立。

于 2018-07-10T03:24:07.933 回答