1

我尝试在 Python 中实现下一个伪代码（来自用于插入排序的俄语页面）：

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

我有一个错误： Traceback（最近一次调用最后一次）：文件“insertion.py”，第 6 行，在 test_sort self.assertEqual(sort( [ 5, 2, 6, 3, 7 ] ), [ 2, 3, 5 , 6, 7 ] ) 文件“insertion.py”，第 12 行，排序键 = a[i] IndexError: list index out of range

我的 sort() 代码是：

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

如果我更改 range() 调用的参数：

for i in range( 2, len_a )

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

[5, 2, 3, 6, 7]

我的代码是错误的还是文章中的算法不准确？

更新。

我更改了代码（使用 0-indexed 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,2,3,6,7]

决议。

我们找到了解决方案：

while j and a[ j ] > key

应该是

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

2 回答 2

4

[5, 2]也不起作用。如果您只是检查while j (>0)，您将永远不会移动第一个项目。我认为这行得通

while j >= 0 and a[ j ] > key:
于 2013-07-04T08:23:13.577 回答
2

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

您需要将两个索引都减一：

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

和

while j >= 0 and a[j] > key:
于 2013-07-04T08:04:05.407 回答