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))

Python 氣泡排序法範例 bubble sort

氣泡排序法是一種排序演算法，

今天就藉由 Python 來介紹下：

Python 氣泡排序法範例 bubble sort

在數列中第一個數開始，

選擇相鄰的兩個數做比較，

只要兩者順序與要求的順序不對，

就交換兩者位置，

直到數列結束，

接著從數列中選擇第二個數進行比較，

重複上述步驟，

如此一來，

數列就會以最大值(或是最小值)排好。

透過之前介紹過的 Python Tutor,

可以實際觀看程式運行過程中各個值變化情形，

底下為實際的程式演示，有興趣可以點 Forward觀察看看：

除了氣泡排序法以外，

還有其他有名的排序法，

比如選擇排序法、插入排序法等等，

這些都是基礎的 sorting 演算法。


當然，

直接使用 Python 的 sort()方法更加快速，

既然是學習，既然是做研究，

了解 sorting 的原理也不是什麼壞處，

就當作練習寫 sort 吧。