选择排序算法

算法简介

选择排序是一个简单直观的排序方法，它的工作原理很简单，首先从未排序序列中找到最大的元素，放到已排序序列的末尾，重复上述步骤，直到所有元素排序完毕。

算法描述

  1. 假设未排序序列的第一个是最大值，记下该元素的位置，从前往后比较
  2. 若某个元素比该元素大，覆盖之前的位置
  3. 重复第二个步骤，直到找到未排序的末尾
  4. 将未排序元素的第一个元素和最大元素交换位置
  5. 重复前面几个步骤，直到所有元素都已经排序。

算法分析

选择排序的交换操作次数最好情况已经有序为0次，最坏情况逆序n-1次，因此交换操作次数位于0 —— (n-1)次之间；比较操作次数（n-1+…+2+1+0. 为n(n-1)/2次；交换元素赋值操作为3次，逆序需要n-1趟交换，因此，赋值操作位于0 —— 3(n-1)次之间。由于需要交换位置，所以肯定是不稳定的。

时间复杂度均为o(n^2) 空间复杂度为o(1) 不稳定

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function selsetSort(arr){
	let len = arr.length;
	let index;
	for(let i=0;i<len-1;i++){
		index=i;
		for(let j=i+1;j<len;j++){
			if(arr[index]>arr[j]){//寻找最小值
				index=j;//保存最小值的索引
			}
		}
		if(index!=i){
		[arr[i], arr[index]] = [arr[index], arr[i]]
	}
	}
	return arr;
}