对于经典算法，你是否也遇到这样的情形：学时觉得很清楚，可过阵子就忘了？
本系列文章就尝试解决这个问题。
研读那些排序算法，细品它们的名字，其实都很贴切。
比如选择排序，所谓“选择”，就是每次遍历时，选择一个最小的交换到已排好序列的后面。
上图演示了第三次遍历，此时元素1和2已经排好序，再在剩下的元素中找到最小的元素3，然后与目标位置交换。
可以看出该算法的核心是：如何在未排好序的元素中找到最小的元素？
这一点难不倒我们，熊瞎子劈苞米，搞个变量记录最小下标。
let array = [1, 2, 4, 5, 3]
let minIndex = 2
for (let i = 2; i < array.length; i++) {
if (array[minIndex] > array[i]) {
minIndex = i
}
}
console.log(minIndex) // 4
找到了最小元素，然后再与目标位置的数据进行交换即可（如果恰好正在目标位置就不用交换了）：
if (minIndex !== 2) {
swap(array, 2, minIndex)
}
console.log(array) // [1, 2, 3, 5, 4]
其中swap函数封装了两个元素如何交换：
function swap(array, i, j) {
[array[i], array[j]] = [array[j], array[i]]
}
每次遍历都排好一个最小的，n次遍历就能排好所有，可以轻松写出代码：
let array = [4, 5, 3, 2, 1]
for (let j = 0; j < array.length; j++) {
let minIndex = j
for (let i = j; i < array.length; i++) {
if (array[minIndex] > array[i]) {
minIndex = i
}
}
if (minIndex !== j) {
utils.swap(array, j, minIndex)
}
}
完整流程示意如下：
image.png
上述代码，还有优化的空间，比如只需要遍历n-1次就行了，因为最后一次，必然剩下了一个元素，不需要再做处理。
完整代码：
const utils = {
swap(array, a, b) {
[array[a], array[b]] = [array[b], array[a]]
},
randomNum() {
return Math.floor(Math.random() * 100)
},
randomArray() {
return Array.from(Array(this.randomNum()), _ => this.randomNum())
}
}
function insertionSort(array) {
for (let i = 1; i < array.length; i++) {
let j = i
let target = array[j]
while(j > 0 && array[j-1] > target) {
array[j] = array[j-1]
j--
}
array[j] = target
}
return array
}
let array = utils.randomArray()
console.log(insertionSort(array))
至此，选择排序原理和实现已经说完了。
这里总结一下，选择排序不需要额外空间，是本地排序，相等元素是不会交换前后顺序，因而也是稳定排序，时间复杂度为O(n^2)，适用于少量数据排序，但实际中用得不多。
网友评论