选择排序

定义

选择排序是一种原地比较排序算法。它将输入数组分为一个已排序子数组和一个未排序子数组。然后，它重复地在未排序子数组中找到最小元素，并将其与未排序子数组中最左边的元素进行交换，将子数组边界向右移动一个元素。

实现

• 使用扩展运算符（...）克隆原始数组arr。
• 使用for循环遍历数组中的元素。
• 使用Array.prototype.slice()和Array.prototype.reduce()来找到当前索引右侧子数组中最小元素的索引。如果需要，执行交换。

const selectionSort = arr => {
  const a = [...arr];
  for (let i = 0; i < a.length; i++) {
    const min = a
      .slice(i + 1)
      .reduce((acc, val, j) => (val < a[acc] ? j + i + 1 : acc), i);
    if (min !== i) [a[i], a[min]] = [a[min], a[i]];
  }
  return a;
};

selectionSort([5, 1, 4, 2, 3]); // [1, 2, 3, 4, 5]

复杂度

该算法的平均时间复杂度为O(n^2)，其中n是输入数组的大小。