Python: 对数组进行插入排序

[jwenjian]

算法导论 第二章

Python实现:

arr = [5, 2, 4, 6, 1, 3]

for i in range(1, len(arr) + 1):
    for j in reversed(range(1, i)):
        if arr[j - 1] > arr[j]:
            arr[j - 1], arr[j] = arr[j], arr[j - 1]

print(arr) # [1, 2, 3, 4, 5, 6]

上述命令输出:

before =      [5, 2, 4, 6, 1, 3]
after =       [2, 5, 4, 6, 1, 3]

before =      [2, 5, 4, 6, 1, 3]
after =       [2, 4, 5, 6, 1, 3]

before =      [2, 4, 5, 6, 1, 3]
after =       [2, 4, 5, 1, 6, 3]

before =      [2, 4, 5, 1, 6, 3]
after =       [2, 4, 1, 5, 6, 3]

before =      [2, 4, 1, 5, 6, 3]
after =       [2, 1, 4, 5, 6, 3]

before =      [2, 1, 4, 5, 6, 3]
after =       [1, 2, 4, 5, 6, 3]

before =      [1, 2, 4, 5, 6, 3]
after =       [1, 2, 4, 5, 3, 6]

before =      [1, 2, 4, 5, 3, 6]
after =       [1, 2, 4, 3, 5, 6]

before =      [1, 2, 4, 3, 5, 6]
after =       [1, 2, 3, 4, 5, 6]

[1, 2, 3, 4, 5, 6]

排序过程:

---

Gist中还有另外一种实现: arr-sort.py