python怎么實現最簡單的選擇排序

# Python怎么實現最簡單的選擇排序

選擇排序（Selection Sort）是最基礎的排序算法之一，其核心思想是每次從未排序部分選出最?。ɑ蜃畲螅┰?，放到已排序部分的末尾。本文將詳細介紹如何用Python實現最簡單的選擇排序，并分析其時間復雜度和適用場景。

---

## 一、選擇排序算法原理

### 1. 算法步驟
1. **初始狀態**：整個數組分為已排序區（空）和未排序區（完整數組）
2. **迭代過程**：
   - 在未排序區中找到最小元素
   - 將該元素與未排序區的第一個元素交換位置
   - 已排序區長度+1，未排序區長度-1
3. **終止條件**：未排序區只剩1個元素時自動有序

### 2. 動態示意圖

初始：[64, 25, 12, 22, 11] 第1輪：[11, 25, 12, 22, 64] # 11與64交換 第2輪：[11, 12, 25, 22, 64] # 12與25交換 第3輪：[11, 12, 22, 25, 64] # 22與25交換 第4輪：[11, 12, 22, 25, 64] # 已有序

---

## 二、Python實現代碼

### 基礎實現版本
```python
def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):  # 只需要n-1輪
        # 找到未排序部分的最小值索引
        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

# 測試用例
print(selection_sort([64, 25, 12, 22, 11]))  # 輸出 [11, 12, 22, 25, 64]

優化版本（同時找最小和最大值）

def selection_sort_optimized(arr):
    n = len(arr)
    for i in range(n//2):
        min_idx, max_idx = i, n-i-1
        for j in range(i+1, n-i):
            if arr[j] < arr[min_idx]:
                min_idx = j
            if arr[j] > arr[max_idx]:
                max_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        # 處理最大值可能被移動的情況
        if max_idx == i:
            max_idx = min_idx
        arr[n-i-1], arr[max_idx] = arr[max_idx], arr[n-i-1]
    return arr

三、算法分析

時間復雜度

空間復雜度

• O(1)（原地排序）

穩定性

• 不穩定排序（交換可能改變相等元素的相對位置）

四、選擇排序的特點

優點

1. 實現簡單直觀
2. 不占用額外內存空間
3. 對于小規模數據效率尚可

缺點

1. 時間復雜度較高，不適合大數據量
2. 不穩定排序
3. 無論輸入數據是否有序，都需要完成全部比較

五、選擇排序 vs 冒泡排序

六、實際應用場景

1. 教學演示基礎排序原理
2. 數據量極?。╪ < 100）的排序需求
3. 內存嚴格受限的環境
4. 需要減少交換次數的場景（如交換成本高的數據結構）

七、擴展練習

1. 嘗試實現降序排列版本
2. 修改算法使其變為穩定排序
3. 用選擇排序實現字符串數組的字典序排序
4. 比較選擇排序與插入排序的性能差異

選擇排序雖然簡單，但包含了算法設計中”選擇-交換”的核心思想，是理解更復雜排序算法的重要基礎。 “`