概念
选择排序(selection sort) 是一种简单直观的排序算法。
选择排序动图（copy）.jpg
原理
第一次从待排序的数据元素中选出最小(或最大)的那个元素，存放到序列的起始位置，然后再在剩余的未排序的元素中选出最小(或最大)的元素，放到已经排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为0。
步骤：
- 初始状态：无序区域为[1....n],有序区域为空；
- 第i（i=1,2,3...n）趟排序开始时，当前有序区域和无序区域为[1...i-1]和[i...n]。这趟排序从无需区域中选出最小的的记录min,将它和无序区域的第一个值交换，使得有序区域+1，无序区域-1.
-
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;
}
