簡單插入的邏輯僵局Sort

我在教自己的Python，我遇到了一個相對簡單的概念。目標是使用插入排序以升序對列表進行排序。這裏是代碼：簡單插入的邏輯僵局Sort

def InsertionSort(A): 
    for j in range(1, len(A)): 
     key = A[j] 
     i = j - 1 
     while (i >=0) and (A[i] > key): 
      A[i+1] = A[i] # this is the not understood point 
      i = i - 1 
     A[i+1] = key 
    print A

我不明白粗體步驟是如何工作的。例如，如果我有一個[6,5,4,3,1]的列表，並且我已經進行了第二次迭代，那麼現在我的列表是不是[6,6,4,3,1]？我分配A [i + 1]（在第一種情況下它將是5）A [i]的值（在第一種情況下爲6）。我的5發生了什麼事？我最初的代碼嘗試是：

def InsertionSort(A): 
    for j in range(1, len(A)): 
     key = A[j] 
     i = j - 1 
     while (i >=0) and (A[i] > key): 
      temp = A[i+1] 
      A [i+1] = A[i] 
      A[i] = temp 
      i = i - 1 
     A[i+1] = key 
    print A

此方法也可以。我不明白爲什麼第一個人也會這樣做。任何人都想刺？

來源

2011-08-07 mv2323

的算法的研究！ =對給定編程語言的研究。你使用Python的事實只是偶然的問題，這是關於理解算法實現的邏輯。 –

如果你開始[6,5,4,3,1]迭代次數將作如下安排：

第一步：

[6,5,4,3,1] 
    ## first number sorted`

第二步（j=2）：

key <- 5 

A <- [6,6,4,3,1], i <- -1 
    ## the 5 will be overridden but is still save in the key variable 

A <- [5,6,4,3,1]   
    ## A[i+1] = key will restore the 5

的唯一價值，可以得到「丟失「是包含在A[j]中的一個。但是這個值總是保存在變量key中，因此可以在最後一步中恢復。

來源

2011-08-07 11:25:36 Howard

@ mv2323：問題在於'key'記得你在循環結束時恢復的值，所以你不會丟失信息。 –

我認爲這只是因爲行A[i+1]=key。

第一種算法將執行以下操作：考慮名單[1,2,4,5,3]，假設我們是在迭代哪裏j=4，即我們正在考慮列表元素3。該algorighm存儲元件3在key並檢查以下內容：

[1,2,4,5,3] 
    ^ 5>3 (key) => move 5 forward by 1 => [1,2,4,5,5] 
[1,2,4,5,5] 
    ^ 4>3 (key) => move 4 forward by 1 => [1,2,4,4,5] 
[1,2,4,4,5] 
^  2<3 => stop inner while loop 
now, make A[i+1]=key (remember: key is 3): 
[1,2,3,4,5]

在與上述相反，第二算法實際上互換元件在每次迭代中：

[1,2,4,5,3] 
    ^ 5>3 (key) => swap 5 and 3 => [1,2,4,3,5] 
[1,2,4,3,5] 
    ^ 4>3 (key) => swap 4 and 3 => [1,2,3,4,5] 
[1,2,3,4,5] 
^  2<3 => stop while loop 
now, make A[i+1]=key (remember: key is 3): (this is unnecessary!) 
[1,2,3,4,5]

來源

2011-08-07 11:27:17 phimuemue

完美，明白了。 – mv2323

簡單插入的邏輯僵局Sort

回答

相關問題