昨天講了插入排序法，今天就接著介紹選擇排序法 (Selection Sort) & 氣泡排序法 (Bubble Sort)，兩個基礎的排序演算法。(以下都為升序)

選擇排序法 (Selection Sort)

選擇排序法 (Selection Sort) 簡單來講就是

• 找到最小的，跟第一個換位置
• 找到第二小的，跟第二個換位置
• 找到第三小的，跟第三個換位置
• 依此類推直到全部換完

圖例如下：

1. 先選第一個位置的「10」當準備要被換的
   

2. 從「10」的右邊找到最小的「1」後交換位置
   

3. 交換完畢後到第二個位置的「6」當準備要被換的
   

4. 發現沒有更小的換到第三個位置「8」
   

5. 發現沒有更小的換到第四個位置「13」
   

6. 從「13」的右邊找到最小的「10」後交換位置
   

7. 交換完畢後到第五個位置的「13」當準備要被換的
   

8. 然後從「13」的右邊找到最小的「10」後交換位置
   

9. 因為前面已經都是比第六個小的，所以排序完成！
   

參考程式碼

def selection_sort(unsorted):
    for i in range(len(unsorted)-1): # 最後只需要到倒數第 2 個，因為前面的排完之後最後一個一定最大

        min_index = i    # min_index 就是最小值的 index

        for j in range(i+1, len(unsorted)): # 從 i+1 開始，因為不需要和自己比
            if unsorted[min_index] > unsorted[j]:
                min_index = j # 如果找到更小的就把 min_index 改成它

        if min_index != i:  # 自己不用跟自己換 
            unsorted[min_index], unsorted[i] = unsorted[i], unsorted[min_index]

    return unsorted

nums = list(map(int, input("請輸入一串數字（以空格隔開）：").split()))
print("未排序資料：", nums)
print("排序後：", selection_sort(nums))

氣泡排序法 (Bubble Sort)

顧名思義，就是資料向氣泡一樣一直慢慢往上，氣泡越大上升的速度大 (應該吧？)

資料的數字越大，就代表氣泡越大所以就會先跑到最上面，再來就第二、第三...

大概就是

• 第一輪
  • 選定第一個，如果比下一個大就交換，反之則不動
  • 選定第二個，如果比下一個大就交換，反之則不動
  • 依此類推，換到最後一個時最大的就在後面
• 第二輪，一樣上面的操作，第二大的就會到倒數第二個
• 第三輪，一樣上面的操作，第三大的就會到倒數第三個
• 以此類推，直到排序完成

圖例如下

1. 第一輪，從第一個開始
   

2. 比下一個大就交換
   

3. 比下一個大就交換
   

4. 比下一個小就換下一個當氣泡
   

5. 比下一個大就交換
   

6. 比下一個大就交換
   

7. 第二輪，重複上面操作，氣泡排到「11」前面
   

8. 第三輪
   

9. 第四輪，排序完成！
   

參考程式碼

def bubble_sort(unsorted):
    for i in range(len(unsorted)):

        # swapped 代表當前輪次有沒有交換，因為 bubble sort 特性沒有交換就但表已完成排序
        swapped = False  

        for j in range(len(unsorted)-i-1): # -1 因為最後一輪只有一個需要跑 (自己跟自己比)

            if unsorted[j] > unsorted[j+1]:
                unsorted[j], unsorted[j+1] = unsorted[j+1], unsorted[j]
                swapped = True # 有交換就設為 True

        if swapped == False: # 沒交換就直接結束
            break

    return unsorted


nums = list(map(int, input("請輸入一串數字（以空格隔開）：").split()))
print("未排序資料：", nums)
print("排序後：", bubble_sort(nums))

謝謝！

參考資料
增井敏克，《圖解演算法原理》，碁峰資訊，2023 年