談談插入排序(Insertion Sort)

在開始今天之前，先來看看影片（約2分鐘）吧！

https://www.youtube.com/watch?v=OGzPmgsI-pQ

插入排序是從數列的左邊開始，往右往右依次排序下去。過程中，左邊的數一一完成排序，右邊剩下尚未確認的數。在右邊尚未搜尋的領域中取出一個數，插入已排序完成的領域中的適當位置。

若取出的數比排序完成領域中的所有的數都小，這個數移動到最左邊之前，要進行比較和對調，第k回合必須進行k-1次的比較和對調的操作，因此最糟情況是第n回合發生n-1次的比較和對調，所以執行時間和氣泡排序及選擇排序一樣是O(n^2)

import random

#從1-100中隨機讀取9個數字
nums = random.sample(range(1,100), 9)
print(nums)

# i控制j的上限值
for i in range(1, 9):
    #初始化變數nums[i]
    insert = nums[i]
    j = i-1
    #內層迴圈從i-1到0，每次遞減1
    while j>=0:
        if insert < nums[j]:
            nums[j+1]=nums[j]
        else:
            break 
        j = j-1
    #將變數insert儲存到nums[j+1]
    nums[j+1]=insert
    print("插入排序執行次數為：", i ,"次")
    for item in nums:
        print(item,' ',end="")

插入排序法的最佳情況與最差情況：

1. 最佳情況：

   • 比較次數：O(n)
   • 設定次數：O(n)
   • 說明：假設資料要以由小到大排序，輸入資料也是以小到大，則為最佳情況。

2. 最差情況：

   • 比較次數：O(n^2)
   • 設定次數：O(n^2)
   • 說明：假設資料要以由小到大排序，輸入資料是以大到小，則為最差情況。