我想知道这是为什么 –费曼
选择排序，是每次遍历都选最小的一个数交换到已经排好的序列的后面
有点像从小到大，依次找到每个位置上正确的数
5 4 3 2 1
第一次遍历发现最小的是 1
把 5 和 1 交换
1 4 3 2 5
第二次遍历从 4 开始（1 已经是排好的序列了）开始发现在（4 3 2 5）里最小的是 2
把 4 和 2 交换
1 2 3 4 5
第三次遍历从 3 开始在（3 4 5）里 3 已经是最小的了，这次不交换
第四次遍历从 4 开始，同上发现 4 也已经是最小的了
第五次最后这次遍历不用做了，在前面都是从小到大排好序的，最后这个数字就是最大的
我们开始写代码：
1
2
3
4
5
6
7
8
|
//先看在一次遍历里做了什么
let minNumberIndex = 0
for (let i = 0; i < array.length; i++) {
if (array[i] < array[minNumberIndex]) {
minNumberIndex = i
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
function selectionSort(array) {
for (var j = 0; j < array.length - 1; j++) {
let minNumberIndex = j
for (let i = j; i < array.length; i++) {
if (array[i] < array[minNumberIndex]) {
minNumberIndex = i
}
}
if (minNumberIndex !== j) {
;[array[i], array[minNumberIndex]] = [array[minNumberIndex], array[i]]
}
}
return array
}
|
选择排序和冒泡排序很类似都是在每一次遍历的时候去找最大或者最小的值，然后把找到的值去（通过交换）排好序列，
下一次的遍历从余下的数字里进行
总结：
选择排序不需要额外空间，是本地排序，相等元素是不会交换前后顺序，因而也是稳定排序，时间复杂度为 O(n^2)，适用于少量数据排序，但实际中用得不多
非常感谢老姚的文章：
手写算法并记住它：选择排序
