排序 - 选择排序

概念

选择排序算法就是不断地遍历数组中未排序的部分，从中选出最小的数字，换到未排序部分的开头。

算法

1. 从第一个数字开始遍历数组，同时记录当前遍历中遇到的最小的数字。

2. 一轮遍历结束后，把最小的数字和数组的第一个数字交换位置。

3. 接着从第二个数字开始遍历，找出剩余数组中的最小数字，与第二个数字交换位置，重复以上步骤，直到数组中所有数字都已排序。

复杂度

• 时间复杂度：$O(n^2)$，无论数组是否已经排好序，时间复杂度都是这个，因为每个数字都差不多要跟数组中的其他数字比较一次。

• 空间复杂度：$O(1)$。

应用

• 待排序数组比较小，不计较时间复杂度的时候可以用。

• 如果排序方案要求每个数字都要跟数组中的其他数字做一次比较，可以考虑选择排序。

• 写操作(交换数字)次数有限制时可以考虑，相较冒泡排序中的 $O(n^2)$ 次交换元素的操作，选择排序中只需要 $O(n)$ 次。

代码

JavaScript Code

function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let minIndex = i;
        for (let j = i; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) minIndex = j;
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
}