Insertion Sort -读取MIT Intro to Algos的问题

Question

MIT Intro to Algorithms将插入排序描述为：

​

​

我用Python写了这段代码：

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

        # i > 0 should be i >= 0
        while i > 0 and A[i] > key:
            A[i + 1] = A[i]
            i = i - 1;
        A[i + 1] = key

    return A

然而，while i > 0这一行引入了一个错误--前两个键放错了位置。将其更改为while i >= 0可以解决此问题。

为什么这不包括在麻省理工学院的入门书中？我是不是读错了？

Answer 1

书中的算法假设索引从1到A.length，这就是为什么它从索引2开始。Python具有从0到len(A) - 1的数组索引。您在range中对此进行了更正，但在循环测试中却忽略了对其进行更正。这样做可以解决问题。

Answer 2

@pjs是完全正确的。我要补充的是，将为基于1的数组编写的算法转换为基于0的算法的一种有条不紊的方法是，在每个数组引用处按原样使用算法，但减去1，然后使用代数来简化。在这里，你最终会得到：

def sort(A):
  for j in range(2, len(A) + 1): # +1 is because Python ranges exclude high limit
    key = A[j - 1]
    i = j - 1
    while i > 0 and A[i - 1] > key:
      A[i + 1 - 1] = A[i - 1]
      i = i - 1
    A[i + 1 - 1] = key
  return A

当然，通过删除+ 1 - 1很容易简化，因为这是在添加零！结果运行良好。

如果您想使外部范围从1开始而不是从2开始，使代码更美观，请将替换设置为jj = j - 1，这(两边加1)表示j = jj + 1

def sort(A):
  for jj in range(1, len(A)):
    key = A[jj + 1 - 1]
    i = jj + 1 - 1
    while i > 0 and A[i - 1] > key:
      A[i] = A[i - 1]
      i = i - 1
    A[i] = key
  return A

再次删除+ 1 - 1%s，我们有

def sort(A):
  for jj in range(1, len(A)):
    key = A[jj]
    i = jj 
    while i > 0 and A[i - 1] > key:
      A[i] = A[i - 1]
      i = i - 1
    A[i] = key
  return A

这看起来很棒，我就到此为止吧。但是，使用替代ii = i - 1或i = ii + 1也可以实现另一种变体。

def sort(A):
  for jj in range(1, len(A)):
    key = A[jj]
    ii + 1 = jj 
    while ii + 1 > 0 and A[ii + 1 - 1] > key:
      A[ii + 1] = A[ii + 1 - 1]
      ii + 1 = ii + 1 - 1
    A[ii + 1] = key
  return A

嗯..。那些分配给ii的任务看起来很奇怪。但是我们可以再一次用代数把所有的东西都理顺。

def sort(A):
  for jj in range(1, len(A)):
    key = A[jj]
    ii = jj - 1  # Subtracted 1 from both sides
    while ii >= 0 and A[ii] > key: # x + 1 > 0 iff x >= 0
      A[ii + 1] = A[ii]
      ii = ii - 1 # Subtracted 1 from both sides and simplified
    A[ii + 1] = key
  return A

瞧，我们有你提议的代码。每次都有效。