algorithm - 与我已经证明的相比，有人可以为我提供更好的冒泡排序证明和场景吗

Question

给出未排序元素的列表。初始条件是 A=未排序元素的列表，p=1，N=总数组大小

Bubble(A,p,N)
 if p>=N return
 for i=p to N-1
  if A[i]>A[i+1]
   swap(A[i],A[i+1])
 Bubble(A,p,N-1)

问题一:通过对N的归纳证明算法的正确性。我的问题:如何在 Bubble(A,p,N-1) 上使用 k+1？我需要有人为我解释和证明。

问题 2:证明如果一个元素一旦向 n 移动，则对于当前和所有即将进行的递归调用，它永远不会向 p 移动。(未解决)

我的问题:我知道在完成排序的第一个n-1 for循环后，数组中最大的整数值将排在最后一个位置。当调用 Bubble(A,p,N-1) 的递归时，数组大小将为 n-1,n-2,...n-n 并且最后的最大整数将不再与下一个和即将到来的递归调用进行比较.(这是一个很好的证明吗？如果没有，谁能给我一个更好的证明？)

问题3:给出一个场景，一个元素向p移动后，可以向n移动。(未解)

我的问题:我知道对于 1 到 n-1 的当前 for 循环，如果 A[i]>A[i+1] 那么它将交换 A[i+1] 最大的位置和 A [i] 将是最小的。然后调用Bubble(A,p,N-1)时，会再次比较n-1数组大小的整数值。如果 A[i]>A[i+1] 则交换。元素将被比较并交换 n-1,n-2,...,n-n。(这是一个好的场景吗？如果没有，谁能给我一个更好的场景？)

Answer 1

Question 1: Prove the correctness of the algorithm by induction on N. My Problem:How can i use k+1 on Bubble(A,p,N-1)?I need someone explain and proof for me.

证明是对 N 的归纳。

基本情况:当 N = 1 时，数组已经排序，并且 Bubble正确地什么都不做并立即终止 if p >= N return .

归纳假设:假设Bubble正确排序大小不超过 k 的列表(强感应)。

归纳步骤:我们必须显示Bubble正确排序大小为 k+1 的列表.关于 Bubble 的初始调用, p小于 N = k+1所以我们跳过算法的第一行。接下来，for可以显示循环(也使用归纳法)具有以下循环不变量:在迭代 i = m 上, A[m+1]将大于或等于 A[1]通过A[m] .因此，循环以 A[1], A[2], ..., A[k+1] 中的最大元素结束。在位置k+1 .如果大小为 k，它将对问题进行递归调用。其中，根据归纳假设，Bubble保证正确排序。自 A[k+1]是最大的元素并且在末尾，因为所有较早的元素都通过对 Bubble 的递归调用正确排序, 证明排序是正确的。

(另一个的归纳证明留作练习。选择 N=2 和 p=1 作为您的基本情况。然后，假设不变量在 k 之前都为真。显示 k+1。通过争论 swap 的作用。然后，根据 p 假定的最后一个值，说出数组的最终状态必须是什么。)

Question 2:Prove that if an element once moves towards n, it will never move towards p for current and all forthcoming recursive calls.(unsolved)

反证法。考虑位置 i 处的元素在一些调用的开始 Bubble被 swap 感动了在 for 中循环到位置 j > i .进一步假设 swap s 在同一调用中，或 swap s 在 Bubble 的另一个调用中, 使该元素的位置变为 k与 k < j .我们只需要考虑第一个这样的运动，因为如果有任何运动，那就是第一个。第一个这样的运动是由于 swap在同一调用或 swap在另一个调用中。分别考虑这些情况。

1. swap当前调用中的 s 只能向前移动元素，不能向后移动。由于在此调用期间交换的元素永远不可能是任何交换的“下一个”元素，因此它不能向后移动。

2. swap s 在 Bubble 的其他调用中可能会移动该元素，因为该元素将成为潜在 swap 之一的“下一个”元素;然而，这永远不会发生，因为这意味着数组中较早的元素有一个更大的元素，它会在之前调用“bubble”时“冒泡”通过所讨论的元素。我们假设我们的元素之前移动到了右边，这意味着它是迄今为止看到的最大的元素。

因为这是元素可以移动到 p 的仅有的两种方式而这些都不可能，我们有一个矛盾，这意味着我们假设元素可以向 p 移动是假的。

编辑:对于问题 3，考虑数组 [3, 2, 1] 的情况。第一次交换交换 3 和 2，将 2 移向 p。第二次交换交换 3 和 1，将 1 移向 p。 Bubble 递归调用的第一次交换交换 1 和 2，将 2 移回 n。通常，您会在很多情况下从反向排序的数组开始获得所描述的行为。