有人可以爲我提供一個更好的證明和場景泡沫分類比較我已經證明

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) 

問題1：通過感應上N. 我的問題證明了該算法的正確性：我怎樣才能使用k Bubble上的+1（A，p，N-1）？我需要有人爲我解釋和證明。

問題2：證明，如果一個元素一旦對n步，它將永遠不會向P代表當前和即將所有遞歸調用移動（未解決）

我的問題：我知道，完成第一次正後1爲循環排序，數組中最大的整數值將排序在最後一個位置。當調用Bubble（A，p，N-1）的遞歸時，數組大小將爲n-1，n-2，... nn，並且最後的最大整數將不再與下一個和即將到來的遞歸調用進行比較（這是一個很好的證明。如果沒有誰能給我提供一個更好的證明？）

問題3：給一個場景，一個元件朝向p運行後，它可以向n遷移（未解決）

。我的問題：我知道，對於1到n-1的當前循環，如果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，...，nn，元素將進行比較和交換（這是一個好場景嗎？如果沒有人能提供給我更好的場景嗎？）

Answer 1

問題1：證明通過N上的歸納法算法的正確性。我的問題：我如何在氣泡上使用k + 1（A，p，N-1）？我需要某人爲我解釋和證明。

證明是通過感應上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。通過爭論swap做什麼來證明它爲k+1。然後，根據由p假定的最後一個值，說陣列的最終狀態應該是什麼）

問題2：證明，如果一個元素一旦對n步，它將永遠不會向且移動當前（未解決）

證明是矛盾的。考慮位於i處的元素，在Bubble的一些調用的開始處，由for循環中的swap s移動到位置j > i。假設在同一調用中進一步調用swap，或在另一調用Bubble中調用swap，導致該元素的位置變爲k和k < j。我們只需要考慮第一個這樣的動作，因爲如果有任何第一個動作的話。第一個這樣的移動是由於在同一個調用中的swap或另一個調用中的swap。分別考慮這些情況。

1. swap s在當前調用中只能向前移動元素，而不能向後移動。由於在此調用期間交換的元素不能成爲任何交換的「下一個」元素，因此無法向後移動。

2. swap S IN的Bubble其他調用可能移動元件，由於元件將是潛在swap S的一個「下一個」元件;然而，這絕不會發生，因爲它意味着數組中較早的元素會在先前調用「bubble」時被「冒泡」通過該元素。我們認爲我們的元素在此之前移到了右邊，這意味着它是迄今爲止最大的一個。

因爲這些是僅有的兩種方式的元素可以對p移動，這些都不是可能的，我們有一個矛盾，這意味着我們的假設，即元素可能走向p是假的。

編輯：對於問題3，考慮數組[3,2,1]的情況。第一個交換交換3和2，向p移動2。第二個交換交換3和1，將1移向p。 Bubble交換1和2的遞歸調用的第一次交換，將2移回n。一般來說，你會得到所描述的行爲，很多人是以逆序排列的數組開始的。