← 返回首頁

🎯 選擇排序法

Selection Sort - 可視化演示與詳細解釋

什麼是選擇排序法？

選擇排序法是一種直觀的排序演算法。每次從未排序的部分中找出最小（或最大）的元素，將其放到已排序部分的末尾，直到整個陣列排序完成。

演算法特點

  • 簡單易懂：邏輯清晰，容易理解和實現
  • 原地排序：不需要額外的記憶體空間
  • 不穩定排序：相等元素的相對位置可能改變
  • 效率一般：時間複雜度恆為 O(n²)

排序原理

把陣列分為「已排序」和「未排序」兩個部分。每次從未排序部分找到最小元素，放到已排序部分的末尾。就像在一堆數字中一次次「選出」最小的放在前面。

互動演示

比較次數：0

交換次數：0

當前步驟：就緒

時間與空間複雜度

情景 時間複雜度 說明
最好情況 O(n²) 陣列已排序，仍需進行所有比較
平均情況 O(n²) 隨機排列的陣列
最壞情況 O(n²) 陣列反向排序，需要所有比較
空間複雜度 O(1) 原地排序，僅需常數額外空間

詳細步驟

  1. 從未排序部分中找到最小的元素
  2. 將其與未排序部分的第一個元素交換
  3. 這樣最小元素就被放到了已排序部分的末尾
  4. 已排序部分向後擴展一個位置
  5. 重複步驟 1-4，直到未排序部分變空
  6. 整個陣列排序完成

虛擬碼與實際程式碼對照

這裡展示 Selection Sort 的關鍵流程，並比較虛擬碼與頁面中的 JavaScript 實作。

虛擬碼

function selectionSort(arr):
    n = length(arr)
    for i in 0..n-2:
        minIndex = i
        for j in i+1..n-1:
            if arr[j] < arr[minIndex]:
                minIndex = j
        swap(arr, i, minIndex)

JavaScript 對照

async function selectionSort() {
    const n = array.length;
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (!isSorting) return;
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            await swap(i, minIndex);
        }
    }
}

程式碼與動畫對應

const n = array.length;                    -> 取得資料長度，準備選擇排序動畫
let minIndex = i;                           -> 將當前未排序區段第一個元素設為最小值候選，動畫標記候選元素
if (array[j] < array[minIndex]) {          -> 比較當前元素與最小值候選，更新候選最小值，動畫標示比較結果
await swap(i, minIndex);                   -> 將最小值交換到已排序區段末端，動畫顯示實際交換動作
}

邊界條件（Boundary Conditions）