插入排序不變斷言失敗

Question

在下面的for循環結束處的代碼中，我使用assert函數來測試[i + 1]是否大於或等於[i]，但我得到以下錯誤（在下面的代碼之後）。同樣在C++中，assert與以下似乎工作得很好，但在python（下面的代碼）它似乎並沒有工作......任何人都知道爲什麼？

import random 

class Sorting: 
    #Precondition: An array a with values. 
    #Postcondition: Array a[1...n] is sorted. 
    def insertion_sort(self,a): 
     #First loop invariant: Array a[1...i] is sorted. 
     for j in range(1,len(a)): 
      key = a[j] 
      i = j-1 
      #Second loop invariant: a[i] is the greatest value from a[i...j-1] 
      while i >= 0 and a[i] > key: 
       a[i+1] = a[i] 
       i = i-1 
      a[i+1] = key 
      assert a[i+1] >= a[i] 
     return a 

    def random_array(self,size): 
     b = [] 
     for i in range(0,size): 
      b.append(random.randint(0,1000)) 
     return b 


sort = Sorting() 
print sort.insertion_sort(sort.random_array(10)) 

的錯誤：

Traceback (most recent call last): 
File "C:\Users\Albaraa\Desktop\CS253\Programming 1\Insertion_Sort.py", line 27, in   <module> 
    print sort.insertion_sort(sort.random_array(10)) 
File "C:\Users\Albaraa\Desktop\CS253\Programming 1\Insertion_Sort.py", line 16, in insertion_sort 
    assert a[i+1] >= a[i] 
AssertionError 

Answer 1

你的代碼沒問題。 i==-1時斷言失敗。在Python中，a[-1]是列表的最後一個元素，因此在這種情況下，您要檢查第一個元素（a[-1+1]）是否大於或等於最後一個元素（a[-1]）。

Answer 2

有在那裏你插入key密切關注。

Answer 3

如何：

import random 

class Sorting: 
    def insertion_sort(self,a): 
     for i in range(1,len(a)): 
      key = a[i] 
      j = i 
      while j > 0 and a[j-1] > key: 
       a[j] = a[j-1] 
       j-=1 
      a[j] = key 
     return a 

    def random_array(self,size): 
     b = [] 
     for i in range(0,size): 
      b.append(random.randint(0,1000)) 
     print b 
     return b 


sort = Sorting() 
print sort.insertion_sort(sort.random_array(10)) 

輸出：

$ ./sort.py 
[195, 644, 900, 859, 367, 57, 534, 635, 707, 224] 
[57, 195, 224, 367, 534, 635, 644, 707, 859, 900]