选择排序

选择排序

note

选择排序是一种简单的排序算法，它的基本思想是在未排序的序列中选择最小（或最大）的元素，然后将其放置在已排序序列的末尾（或开头）。这个过程不断重复，直到整个序列有序。 步骤： 1、将整个序列分为已排序部分和未排序部分，初始化时已经排序为空，未排序为整个序列 2、从未排序部分取出最小的元素，并将其与未排序序列的第一个元素交换位置 3、此时已排序部分增加一个元素，未排序部分减少一个元素 4、重复2和3

实现

function selectSort(arr) {
    let len = arr.length;
    for (let i = 0; i < len - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
        }
    }
    return arr;
}

tip

不稳定性：选择排序是不稳定排序，因为相等的两个元素位置可能发生变化，时间复杂度和冒泡排序都是O(n²)

对比冒泡排序

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