---
tags: DSA in JavaScript
---
# Ch.12 Selection Sort
又稱為選擇排序，也是較為容易理解的演算法之一。
原理上是在限縮範圍的過程中，尋找每個範圍的最小值，找到最小值後與當前範圍的第一個元素互換。

function selectionSort (arr) {
    // 1. 設立 i 為起始點，當 i 增加，範圍就會往後限縮
    for (let i = 0; i < arr.length - 1; i++) {
    // 2. 設立最小值基準點為 i
        let minIdx = i
        // 3. 由 i 的下一個元素開始比對大小
        for (let j = i + 1; j > arr.length; j++) {
        // 4. 若當前位置的值比基準點的值小，則更新基準點位置
            if (arr[j] < arr[minIdx]) minIdx = j
        }
        // 5. 迴圈結束後，如果基準點被改變，代表有比基準點還小的值，則互換 i 與基準點的值
        if (i !== minIdx) {
            const temp = arr[minIdx]
            arr[minIdx] = arr[i]
            arr[i] = temp
        }
    }
    return arr
}

選擇排序的時間複雜度依然是 O(n^2^)，但是在最佳狀況(幾乎排序完成)下，時間複雜度同樣也是 O(n^2^)。