选择排序

概念

选择排序(selection sort) 是一种简单直观的排序算法。

选择排序动图（copy）.jpg

原理

第一次从待排序的数据元素中选出最小(或最大)的那个元素，存放到序列的起始位置，然后再在剩余的未排序的元素中选出最小(或最大)的元素，放到已经排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为0。

步骤：

1. 初始状态：无序区域为[1....n],有序区域为空；
2. 第i（i=1,2,3...n）趟排序开始时，当前有序区域和无序区域为[1...i-1]和[i...n]。这趟排序从无需区域中选出最小的的记录min,将它和无序区域的第一个值交换，使得有序区域+1，无序区域-1.

3. n-1趟结束后，数组就变成有序的了。

   
   选择排序流程图.jpg

---

时间复杂度： 如果是正序的，时间复杂度是O(n),若不是，则为O(n²)

算法稳定性：序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法

因为交换所需要的cpu比比较所需的cpu时间多，所以选择排序（最多n-1）比冒泡排序快

算法实现

function selectionSort(arr) {
    // 判断是否是数组，不是则抛出错误
    if(!Array.isArray(arr)) {
        throw new Error('传入的不是数组')
    }

    const len = arr.length;

    // 判断长度是否小于等于1，是则直接返回
    if(len <= 1) {
        return arr;
    }

    /*
        定义一个最小值的索引minIndex，如果后边有值比当前值小，则将索引赋值给minIndex， 
    */
    for (let i = 0; i < len-1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if(arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }

        // 不相等的时候才进行交换
        if(i !== minIndex) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }

    return arr;
}

github算法地址