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]));

参考资料