Chen Yufei’s blog

昨天用 python 写 insertion sort 练练手，在用 for 循环的时候遇到了一点小问题。

Dive Into Python 这本书的确不适合初学程序设计的人，我看完第 6 章都没有看到 python 中的 while 语句，所以最初我用了两个 for 循环来实现，xrange 也是我看别人的程序的加上查文档才知道怎么用的。对有经验的人来说这样也没什么不好，python 的语言和类库参考都不错，直接查也很方便。

最初的实现出错了，代码如下：

def insertion_sort(list):
    for i in xrange(1, len(list)):
        key = list[i]
        for j in xrange(i - 1, -1, -1):
            if key < list[j]:
                list[j + 1] = list[j]
            else:
                break
        list[j + 1] = key
    return list

随便试了几个就错了，很奇怪为什么会出错。后来才意识到使用 for 遍历的是一个列表，如果没有 break，遍历完之后 j 是列表中的最后一个元素 0，而不是 -1。如果因为列表遍历完成而非 break 中断循环，则最后应该执行 list[0] = key，但实际执行的是 list[1] = key。

这样就有个问题，如何判断 for 循环是正常遍历结束还是被 break 中断的？在 C 中写 for (j = i - 1; j > -1; j--) 最后循环结束的时候 j 为 -1，所以检查 j 的值就可以了。但在 python 里面，j 最小只可能到 0，循环结束时 j 为 0 可能是因为 key >= list[j] 而 break，也可能因为 0 是最后一个元素而终止循环，所以通过检查 j 的值是没法做到的。（因为 python 中 for 的作用是遍历列表等容器，所以不能让 for 与 C 中有相同的行为。）

查了下语言参考，发现 for 语句可以跟一个 else 块，觉得有点奇怪，还没有见过哪个语言有这样的语法的。文档说 else 后面的块在循环条件为假时执行一次，但如果 for 后面的块中因为 break 导致循环结束则这个块不执行。一开始觉得这个 else 没什么用，除非死循环，否则条件总是会变为假，那直接把代码放在 for 外面不就可以了。后来想到这个特性正好可以用来判断循环终止的原因，用个条件变量即可，在 else 代码中改变这个条件变量，然后在后面的代码中检查条件变量的值即可。

最后的代码如下：

def insertion_sort(list):
    for i in xrange(1, len(list)):
        key = list[i]
        outbound = False
        for j in xrange(i - 1, -1, -1):
            if key < list[j]:
                list[j + 1] = list[j]
            else:
                break
        else:
            list[0] = key
            outbound = True
        if not outbound:
            list[j + 1] = key
    return list

当然用一个 while 循环就可以不用这么麻烦了，不过我就是想知道用 for 该怎么解决这个问题。

PS:
wordpress 有没有什么贴代码用的插件？