插入排序算法的Python实现

思路

这里假定对一个数组里的数据进行非递减排序，思路如下：

1. 在原始数组上操作
2. 总共两层循环
3. 第一层循环，从原数组第二个元素开始，正序遍历到数组最后一个元素，每次进行下述第4步的操作
4. 第二层循环，从当前元素逆序遍历到数组开始位置，让当前元素和前一个元素比较，如果当前元素小于前面一个元素，则交换这两个元素，否则立即终止循环

这个过程类似于玩牌时，每抓到一张新牌，就把这张新牌按大小顺序插入到原始牌序列中：

代码

最新代码请参考本人github

def insertionSort(seq):
    print("Insertion Sort Start...")
    if isinstance(seq, list) is False or len(seq) < 2:
        return
    # start from the second element of the original sequnce
    for index in range(len(seq)):
        if index == 0:
            continue
        # from the last element of child sequnce,
        # till the first element of child sequnce,
        # if the element is greater than the previous element,
        # exchange them,
        # if not,
        # stop traverse
        for idx in range(index, -1, -1):
            if(idx == 0):
                break
            if seq[idx] < seq[idx - 1]:
                tmp = seq[idx]
                seq[idx] = seq[idx - 1]
                seq[idx - 1] = tmp
                continue
            break
        print("round " + str(index) + ": " + str(seq))


if __name__ == '__main__':
    seq = [5, 2, 4, 6, 1, 3]
    print("original seq: ", seq)
    insertionSort(seq)
           

代码输出：

original seq:  [5, 2, 4, 6, 1, 3]
Insertion Sort Start...
round 1: [2, 5, 4, 6, 1, 3]
round 2: [2, 4, 5, 6, 1, 3]
round 3: [2, 4, 5, 6, 1, 3]
round 4: [1, 2, 4, 5, 6, 3]
round 5: [1, 2, 3, 4, 5, 6]