Selection sort 選擇排序法

Selection sort 選擇排序法
Categories:
Tags:

複雜度

複雜度 Big O
最差時間複雜度 Worst-case time complexity Big O(n^2)
平均時間複雜度 Average-case time complexity Big theta (n^2)
最佳時間複雜度 Best-case time complexity Big omega (n)
空間複雜度 Space complexity Big O (1)

演算法

1. 將陣列元素中最小的數字移動到最前方

假設第 1 個元素是最小的，比較後方所有的數字，找出是否有比第 1 元素小的其他元素

2. 將最小元素與最前方數字做比較

當找到的最小數字不是本身檢查的數字的話，將最小的數字與最前方做交換

3. 持續這個步驟，將剩餘的陣列元素做比較

持續地將最小元素比較放到最前方的位置，最後就可以得到已排序的陣列

Selection sort 選擇排序法

程式

JavaScript

function selectionSort(sortNumberList) {
    // 最小數字索引
    var minNumberIndex;
    for (var compareSmallestNumberIndex = 0; compareSmallestNumberIndex < sortNumberList.length; compareSmallestNumberIndex++) {
        // 將目前「比較數字索引位置」設定為「最小數字索引位置」
        minNumberIndex = compareSmallestNumberIndex;
        for (var checkSmallestNumberIndex = compareSmallestNumberIndex + 1; checkSmallestNumberIndex < sortNumberList.length; checkSmallestNumberIndex++) {
            // 檢查後方數字是否有比目前數字小
            if (sortNumberList[minNumberIndex] > sortNumberList[checkSmallestNumberIndex]) {
                // 目前「最小數字索引位置」的數字，比檢查的數字還大，將「檢查數字的索引位置」設定為「最小數字索引位置」
                minNumberIndex = checkSmallestNumberIndex;
            }
        }
        if (minNumberIndex !== compareSmallestNumberIndex) {
            // 若「最小數字索引位置」不是目前「比較數字索引位置」，表示最小數字不同，需要將最小數字與目前數字交換
            [sortNumberList[compareSmallestNumberIndex], sortNumberList[minNumberIndex]] = [sortNumberList[minNumberIndex], sortNumberList[compareSmallestNumberIndex]];
        }
    }
    return sortNumberList;
}
console.log(selectionSort([29, 72, 98, 13, 87, 66, 52, 51, 36]));

TypeScript

function selectionSort(sortNumberList: number[]) {
    // 最小數字索引
    let minNumberIndex;

    for (let compareSmallestNumberIndex = 0; compareSmallestNumberIndex < sortNumberList.length; compareSmallestNumberIndex++) {
        // 將目前「比較數字索引位置」設定為「最小數字索引位置」
        minNumberIndex = compareSmallestNumberIndex;

        for (let checkSmallestNumberIndex = compareSmallestNumberIndex + 1; checkSmallestNumberIndex < sortNumberList.length; checkSmallestNumberIndex++) {
            // 檢查後方數字是否有比目前數字小
            if (sortNumberList[minNumberIndex] > sortNumberList[checkSmallestNumberIndex]) {
                // 目前「最小數字索引位置」的數字，比檢查的數字還大，將「檢查數字的索引位置」設定為「最小數字索引位置」
                minNumberIndex = checkSmallestNumberIndex;
            }
        }

        if (minNumberIndex !== compareSmallestNumberIndex) {
            // 若「最小數字索引位置」不是目前「比較數字索引位置」，表示最小數字不同，需要將最小數字與目前數字交換
            [sortNumberList[compareSmallestNumberIndex], sortNumberList[minNumberIndex]] = [sortNumberList[minNumberIndex], sortNumberList[compareSmallestNumberIndex]];
        }
    }

    return sortNumberList;
}

console.log(selectionSort([29, 72, 98, 13, 87, 66, 52, 51, 36]));

參考資料