选择排序（selectSort），顾名思义，每次选择最值进行排序

目录

一、选择排序算法原理

二、选择排序算法分析

三、选择排序算法应用实例

四、选择排序的适用场景

---

一、选择排序算法原理

1.思路

选择排序的实现思路是从未排序序列中找到最小的元素，放到已排序序列的末尾，重复上述步骤，直到所有元素排序完毕。

2.流程描述：（以非递减为例）

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

3.举例：

例：5,4,7,2,9,1,6

第一趟排序 ：1,4,7,2,9,5,6

第二趟排序： 1,2,7,4,9,5,6

第三趟排序:    1,2,4,7,9,5,6

第四趟排序： 1,2,4,5,9,7,6

······

4.动画演示：

二、选择排序算法分析

最好时间复杂度：

O(n²)  第i趟排序需要n-i次比较。n(n-1)/2

最坏时间复杂度：

O(n²)  第i趟排序需要n-i次比较。n(n-1)/2

平均时间复杂度

O(n²)  

空间复杂度

O(1)  原地排序，辅助空间相对于数据量而言是个常数

稳定性

不稳定。[3,3,1]

三、选择排序算法应用实例

设置未排序最小值下标，外层循环表示趟数，内层循环比较最小值和其它数据大小，比最小值小的更改记录下标，直至循环完毕，交换最小值。

//选择排序
function selectSort(arr){var len = arr.length;var index;for(var i=0;i<len-1;i++){index=i;for(var j=i+1;j<len;j++){if(arr[index]>arr[j]){//寻找最小值index=j;//保存最小值的索引}}if(index!=i){var temp =arr[i];arr[i]=arr[index];arr[index]=temp;}}return arr;
}
var arr = [6,4,9,8,1,3,2]
console.log(selectSort(arr));

四、选择排序的适用场景

选择排序的时间复杂度为O(n²)，空间复杂度为O(1)，与冒泡排序复杂度相同，但由于每次选出待排序数据中的最小值（增序）或最大值（降序）插入到当前的有序队列中，相对于冒泡排序减少了交换的次数。当数据量不大，且对稳定性没有要求的时候，适用于选择排序