從今天開始要來理解排序演算法了!簡單來說就是經過一連串的步驟將數字由小排到大或是由大排到小的演算法，下圖列出幾種常見的排序演算法，像是插入排序法、氣泡排序法、合併排序法等等。

圖片來源:https://dev.to/edwardcashmere/sorting-algorithms-2541

今天要介紹的是選擇排序法，先找出數字裡面最小的或最大的數，第一個步驟是先找最小的數字，再跟尚未排序的數字的最左邊的互換。

假設現在有個尚未排序的陣列:[ 29, 10, 14, 37, 13]

• 尚未排序的數字: 29, 10, 14, 37, 13
• 排序好的數字:無

選擇排序法的執行步驟:

1. 發現尚未排序的數字中10為最小值，與尚未排序中最左邊的數字29交換，此時陣列為[10, 29, 14, 37, 13]
   

• 尚未排序的數字: 29, 14, 37, 13
• 排序好的數字:10

2. 發現尚未排序的數字中13為最小值，與尚未排序中最左邊的數字29交換，此時陣列為[10, 13, 14, 37, 29]
   

• 尚未排序的數字有 14, 37, 29
• 排序好的數字:10, 13

以此類推，直到所有數字都由小排到大

圖檔來源:https://visualgo.net/zh/

用js實作選擇排序法

const selectionSort = (arr) => {
    for (let i = 0; i < arr.length - 1; i++) {
        let minIndex = i;
        for (let j = i; j <= arr.length - 1; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
    }
    return arr;
};

selectionSort([29, 10, 14, 37, 13]);

時間複雜度

• 在最差的情況下， 時間複雜度是O(n²)
• 在最佳的情況下 ， 時間複雜度是O(n²)
• 在平均情況下，時間複雜度為 O(n²)

參考資料:Sorting Algorithms