CodeGym /課程 /Python SELF TW /選擇排序

選擇排序

Python SELF TW

等級 58 , 課堂 2

開放

7.1 選擇排序的定義

選擇排序 (Selection Sort) — 是一種排序演算法，它從未排序部分的陣列中找到最小的元素，然後將其與這部分的第一個元素交換位置。這個過程會重複直到整個陣列排序完成。

工作原理：

從陣列的第一個元素開始。
在未排序的部分中找到最小的元素。
將最小的元素與未排序部分的第一個元素交換位置。
對下一個元素重複這個過程，直到整個陣列排序完成。

逐步過程

在陣列中找到最小的元素，並將其與第一個元素交換位置。
對剩下的陣列重複這個過程（從第二個元素開始）。
持續這個過程，直到整個陣列排序完成。

選擇排序的時間和空間複雜度

時間複雜度：

最壞情況: O(n^2) — 發生在元素最初以相反順序或隨機排列時。
平均情況: O(n^2) — 發生在元素隨機排列時。
最好情況: O(n^2) — 即使陣列已經排序，演算法仍會進行相同的比較。

空間複雜度：

O(1) — 因為演算法使用固定數量的附加記憶體（僅用於儲存暫時值的幾個變數）。

7.2 選擇排序的實現

選擇排序的實現非常簡單：

步驟 1：在所有元素中找到最小的，並將其與第一個元素交換位置。

步驟 2：在所有元素，除了第一個之外，找到最小的，並將其與第二個交換位置。

步驟 3：在所有元素，除了第一和第二個之外，找到最小的，並將其與第三個交換位置。

Python實現：


def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 找到未排序部分中最小的元素 min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j
        # 將找到的最小元素與未排序部分的第一個元素交換位置 arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr  # 返回已排序的陣列

# 使用範例：
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("已排序的陣列:", sorted_arr)
# 輸出: 已排序的陣列: [11, 12, 22, 25, 64]

演算法的工作示例：

第一次迭代 (i = 0):
1. 找到未排序部分[64, 25, 12, 22, 11]中的最小元素 (11)。
2. 將11與64交換。
3. 陣列: [11, 25, 12, 22, 64]
第二次迭代 (i = 1):
1. 找到未排序部分[25, 12, 22, 64]中的最小元素 (12)。
2. 將12與25交換。
3. 陣列: [11, 12, 25, 22, 64]
第三次迭代 (i = 2):
1. 找到未排序部分[25, 22, 64]中的最小元素 (22)。
2. 將22與25交換。
3. 陣列: [11, 12, 22, 25, 64]
第四次迭代 (i = 3):
1. 找到未排序部分[25, 64]中的最小元素 (25)。
2. 25已在正確位置，無需交換。
3. 陣列: [11, 12, 22, 25, 64]