选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
算法思路
使用线性查找当前待排序数据，找到最小值
把最小值移动到数组最左边
重复1、2步，直到数组全部完成排序
代码实现
方式一：
使用递归实现，一次循环比较好读，容易理解，但效率较循环低一些
const unsort = [6, 1, 7, 8, 9, 3, 5, 4, 2]
const selectedSort = (arr, index = 0) => {
let min = arr[index]
const len = arr.length
for (let i = index; i < len; i++) {
const temp = arr[i]
if (temp < min) {
arr[index] = temp
arr[i] = min
min = temp
}
}
if (index === len - 1) {
return arr
}
return selectedSort(arr, index + 1)
}
const sorted = selectedSort(unsort)
console.log(sorted)
// console: [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
方式二：
使用循环实现，两次循环，比较不好读，逻辑容易出现纰漏，效率比递归要高
const unsort = [6, 1, 7, 8, 9, 3, 5, 4, 2]
const selectedSort = (arr) => {
const len = arr.length
let min
let temp
for (let i = 0; i < len; i++) {
min = arr[i]
temp
for (let j = i + 1; j < len; j++) {
if (arr[j] < min) {
temp = min
min = arr[j]
arr[j] = temp
arr[i] = min
}
}
}
return arr
}
const sorted = selectedSort(unsort)
console.log(sorted)
// console: [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
理解
选择排序使用线性方式来查找最小值，所以每次循环都会比较n-m(m为循环次数)个数，直到最后一轮只比较一个数字，因此复杂度是（n - 1）+ (n - 2) + (n - 3) ... + 1 ≈ n2 / 2, 忽略非重要项后为O(n2)
发表评论 (审核通过后显示评论)：