Python 插入排序法範例 Insertion Sort

之前介紹過Python 氣泡排序法範例，

今天要來介紹另一種排序方法：

Python 插入排序法範例 Insertion Sort

插入排序法將資料分成已排序、未排序，

以由小到大排序為範例，

依序由未排序中的資料中選值，

插入到已排序中的位置，

從選定值的位置反向比較回來，

若在已排序位置中遇到的值大於等於選定的值，

將在已排序位置中遇到的值右移

用說明得很抽象，

直接利用範例程式實際演練一次，

透過 Back 與 Forward 按鈕，

能夠觀察目前選定的值以及現有 list 中的變化，

當今天遇到的值比選定的值大的時候，

就將數列往後移一格，

這就是今天的主題：

Python 插入排序法範例 Insertion Sort

最後附上插入排序法的範例程式碼：

test_data = [12, 9, 100, 87, 200, 5, 300]

for i in range(1, len(test_data)):
    target = test_data[i]
    j = i - 1    
    while j >= 0 and target < test_data[j]:
        test_data[j + 1] = test_data[j]  # 右移        
        j = j - 1
    test_data[j + 1] = target
    print("Round %d : %s" % (i, test_data))