每日一算法：选择排序
2022-07-23 本文已影响0人
lio_zero
选择排序是一个很容易理解排序算法。
思路：
- 我们选择第一项。然后我们将其与第二项进行比较。如果第二项较小，我们将其与第一项交换。以此类推，我们将第一项与数组中的每一项进行比较。
- 一旦我们知道我们有最小的项，我们就切换到第二个元素，并将它与数组中的每一项进行比较，忽略索引 0，因为我们已经知道这是最小值。以此类推，直到数组结束。
- 如您所见，该算法非常昂贵。它不仅迭代数组的每一项：对于每一项，它都会再次迭代数组。
JavaScript 实现
使用选择排序算法对数字数组进行排序。
- 使用展开运算符（
...）克隆原始数组arr。 - 使用
for循环遍历数组中的元素。 - 使用
Array.prototype.slice()和Array.prototype.reduce()查找当前索引右侧子数组中最小元素的索引，并在必要时执行交换。
const selectionSort = (arr) => {
const list = [...arr]
for (let i = 0; i < list.length; i++) {
const min = list
.slice(i + 1)
.reduce((acc, val, j) => (val < list[acc] ? j + i + 1 : acc), i)
if (min !== i) [list[i], list[min]] = [list[min], list[i]]
}
return list
}
selectionSort([5, 1, 4, 2, 3]) // [1, 2, 3, 4, 5]
此示例来自 30 seconds of code 的 selectionSort
