写在前面
昨天我们学习了最基础的排序算法----冒泡排序，今天呢，我们一起来看一下冒泡排序的进阶算法，选择排序。
大家在学习冒泡排序的时候，会不会觉得冒泡排序很繁琐呢？你看，要两层循环，每次比较都要遍历一次数组，这还好说，但是要交换好多好多次才能正确排序，简直太麻烦了！历史上也有程序员前辈抱怨这个问题，因此，冒泡排序的进阶升级版----选择排序就诞生了。
选择排序：
选择排序的基本思想是：遍历数列，在数列中找到一个最小的元素放在首位，然后再次遍历数列，再剩余的元素中找到最小的放在第二位，以此类推直到正确排序。
这样的话，虽然好像还是需要两层循环，不停遍历数组，但是交换位置的次数好像少了很多！我们举个例子来具体看下：
设数组 arr = [1, 4, 3, 5, 2] ，我们需要将数组中的数字按照从大到小的顺序重新排序。
第一轮排序：
arr = [1, 4, 3, 5, 2]
arr[0] = 1 与 arr[1] = 4 进行比较，1 < 4，1是最小元素，不交换；
arr[0] = 1 与 arr[2] = 3 进行比较，1 < 3，1是最小元素，不交换；
arr[0] = 1 与 arr[3] = 5 进行比较，1< 5，1是最小元素，不交换；
arr[0] = 1 与 arr[4] = 2 进行比较，1 < 2，1是最小元素，不交换。
遍历结束，1为最小元素且在第一位，位置不变。
第一轮排序之后，我们发现最小的数字就在第一位，数组没有变化，还是arr = [1, 4, 3, 5, 2]，接下来我们进行第二轮排序：
第二轮排序：
arr = [1, 4, 3, 5, 2]
arr[1] = 4 与 arr[2] = 3 进行比较，4 > 3，3是最小元素，交换；
arr[1] = 3 与 arr[3] = 5 进行比较（注意此时arr[1]已经变为3了哦 ），3 < 5，3是最小元素，不交换；
arr[1] = 3 与 arr[4] = 2 进行比较，3 > 2，2为最小元素，交换。
遍历结束，最小元素为2且交换到了第二位，数组arr = [1, 2, 4, 5, 3]，接下来进行第三轮排序。
第三轮排序：
arr = [1, 2, 4, 5, 3]
arr[2] = 4 与 arr[3] = 5 进行比较，4 < 5，4是最小元素，不交换；
arr[2] = 4 与 arr[4] = 3 进行比较，4 > 3，3是最小元素，交换；
遍历结束，最小元素为3且交换到了第三位，数组arr = [1, 2, 3, 5, 4]，接下来进行第四轮排序。
第四轮排序：
arr = [1, 2, 3, 5, 4]
arr[3] = 5 与 arr[4] = 4 进行比较，5 < 4，4为最小元素，交换。
遍历结束，最小元素为4且交换到了第四位，选择排序算法结束，数组arr = [1, 2, 3, 4, 5]
只通过这一个例子，大家就能明显看出，在交换次数上选择排序确实比冒泡排序少了很多。
我们来看一下选择排序的特点;
特点一：从待排序数列中获取最小的元素放在已排数据末尾
特点二：n个数进行n - 1 次排序
接下来看一下代码实现：
代码实现：
let arr = [1, 4, 3, 5, 2];
var selectSort = function(arr){
let len = arr.length;
for(let i = 0; i < len - 1; i++){
let index = i;//设置一个指针，保存最小的元素
//这里采用了双指针思想，让指针 j 在指针 i 的后面一位，保证遍历时不会再次遍历已经归位的最小元素
for(let j = i + 1; j < len; j++){
if(arr[index] > arr[j]){
index = j;//让指针保存最小的元素
}
}
let temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
return arr;
}
代码如上。这里使用了双指针思想，把 i 和 j 都假设为一个指针，i 指针指向数组第一个数字，j 指针指向 i 指针后面的元素，当 i + 1 时，j 也会随之+ 1，这样就避免了再次遍历数组时会遍历到我们已经排序完毕的元素，也就是我们放在数组头部的arr[0]。
接下来我们看一下选择排序的时间复杂度和空间复杂度
时间复杂度：
选择排序依然使用两层 for 循环，只是交换元素的次数下降了，所以时间复杂度依然是O(n²)
空间复杂度：
很明显，选择排序的空间复杂度为0(1)
总结
-
特点
（1）特点一：从待排序数列中获取最小的元素放在已排数据末尾（2）特点二：n个数进行n - 1 次排序
时间复杂度与空间复杂度
时间复杂度：O(n²)
空间复杂度：O(1)
OK，选择排序就讲到这里，如果有补充，欢迎大家评论区留言，希望你学得开心，see you soon~
这个系列的其他文章：
前端算法之排序（一）---- 冒泡排序
