插入排序算法的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]