插入排序的伪代码是否正确？

我尝试在Python实现下一个伪代码（从Russian page for insertion sorting）：插入排序的伪代码是否正确？

for i = 2, 3, ..., n: 
    key := A[i] 
    j := i - 1 
    while j >= 1 and A[j] > key: 
     A[j+1] := A[j] 
     j := j - 1 
    A[j+1] := key

我有一个错误：回溯（最近通话最后一个）：文件 “insertion.py”，第6行，在test_sort self.assertEqual（sort（[5,2,6,3,7]），[2,3,5,6,7]）文件“insertion.py”，行12，按照排序key = a [我] IndexError：列表索引超出范围

我的代码的排序（）是：

def sort(a): 
    len_a = len(a) 
    len_a_plus_1 = len_a + 1 
    for i in range(2, len_a_plus_1): 
     key = a[ i ] 
     j = i - 1 

     while j >= 1 and a[ j ] > key: 
      a[ j + 1 ] = a[ j ] 
      j -= 1 
     a[ j + 1 ] = key 

    return a

如果我改变参数的范围（）调用：

for i in range(2, len_a)

...然后我得到不正确的结果：

[5, 2, 3, 6, 7]

是我的代码错误或algorythm在article innacurate？

更新。

我改变了代码（从0索引的Python原理），但它不正常工作：

def sort(a): 
    len_a = len(a) 
    for i in range(1, len_a): 
     key = a[ i ] 
     j = i - 1 

     while j and a[ j ] > key: 
      a[ j + 1 ] = a[ j ] 
      j -= 1 
     a[ j + 1 ] = key 

    return a

输入：[5，2,6，3，7] 输出：[5,1 2，3，6，7]

决议。

我们发现了解决方案：

while j and a[ j ] > key

768,16是

while j >= 0 and a[ j ] > key

来源

2013-07-04 sergzach

请检查Python代码约定：http://www.python.org/dev/peps/pep-0008/#whitespace-in-expressions-and-statements –

[5, 2]也不起作用。如果你只是检查while j (>0)你永远不会移动第一个项目。我想这样的作品

while j >= 0 and a[ j ] > key:

来源

2013-07-04 08:23:13 doctorlove

谢谢。刚刚找到它。 – sergzach

做得好，尤其是。有一些测试:-) – doctorlove

Python使用基于0的索引，使得a[len(a)]超出范围。伪代码使用从1开始的索引。

你需要减少1 都你指数：

len_a = len(a) 
for i in range(1, len_a):

和

while j >= 0 and a[j] > key:

来源

2013-07-04 08:04:05

谢谢。我这样做，但我的测试仍然没有通过。结果是[5,2,3,6,7]，应该是[2,3,5,6,7]。 – sergzach

---应该是'while j> = 0且a [j]>键：' –

@ Radio-：的确;被一个小早餐分心了.. –

插入排序的伪代码是否正确？

回答

相关问题