选择排序

选择排序将数组划分为已排序和未排序两部分。每一轮从未排序区间中找到最小元素，并将它放到区间起点。

实现

function selectionSort(arr) {
  const result = [...arr]

  for (let start = 0; start < result.length - 1; start++) {
    let minIndex = start

    for (let i = start + 1; i < result.length; i++) {
      if (result[i] < result[minIndex]) minIndex = i
    }

    if (minIndex !== start) {
      ;[result[start], result[minIndex]] = [result[minIndex], result[start]]
    }
  }

  return result
}

复杂度

• 时间复杂度：始终为 O(n²)
• 空间复杂度：O(1)，不计算复制输入数组的空间
• 稳定性：通常不稳定

选择排序的交换次数较少。如果写入操作成本较高，它有时比冒泡排序更合适。