概念
选择排序(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;
}
网友评论