Alg1.1. 選擇排序法

以由小到大排序一個數值串列為例，選擇排序法以循序的方法，依序來搜尋一個串列中最小的數值。在每一回合中都會確定一個最小的數值，再從原來「未排序」的串列中取出該數值及存入另一個「已排序」的串列中。最後，經過 n 個回合之後，例如：n 是串列長度或資料筆數，就可以將資料由小到大排序完成。

• 參考檔案：selection_sort.py

# 定義函數
def find_smallest(data):
    smallest = data[0]                           # 以串列索引值0的數值為目前的最小值
    smallest_index = 0

    for i in range(1, len(data)):                # 從串列索引值1開始搜尋整個串列
        if data[i] < smallest:                   # 如果目前的數值比目前的最小值還小時
            smallest = data[i]                   # 將該數值存入最小值變數中
            smallest_index = i                   # 同時也記錄最小值在串列中的索引值

    return smallest_index


def selection_sort(data):
    sorted_data = []

    for i in range(0, len(data)):                # 執行 n 次循序搜尋
        smallest = find_smallest(data)           # 搜尋該回合最小的數值
        sorted_data.append(data.pop(smallest))   # 將最小的數值存入「已排序」的串列中

    return sorted_data


# 呼叫函數
data = [5, 3, 6, 2, 10]
print(data)
print(selection_sort(data))


# 執行結果
[5, 3, 6, 2, 10]
[2, 3, 5, 6, 10]

躍躍欲試

• 使用 Python 的 sorted() 函數:
  • a104: 排序 [參考答案], practice
  • a915: 二维點排序 [參考答案]
  • d583: 幼稚的企鵝 [參考答案]

參考資料

• 寫程式前就該懂的演算法, 第二章, Aditya Y.Bhargava著, 張書華譯, 松崗, ♥️