选择排序

选择排序如何工作？

• 数组长度为 n, 共重复 n-1 轮;
• 第 i 轮: 在未排序区间 [i, n-1] 中找出最小元素, 与位置 i 的元素交换;
• 交换后 [0, i] 已有序, 不再参与后续比较;

选择排序如何实现？

function selectionSort(nums: number[]): void {
  const n = nums.length;
  for (let i = 0; i < n - 1; i++) {
    let k = i; // 未排序区间中最小元素的索引
    for (let j = i + 1; j < n; j++) {
      if (nums[j] < nums[k]) k = j;
    }
    [nums[i], nums[k]] = [nums[k], nums[i]];
  }
}

选择排序的特性是什么？

• 时间复杂度: O(n^2), 比较次数与输入无关;
• 空间复杂度: O(1), 原地排序;
• 稳定性: 非稳定排序, 最小元素与位置 i 的远距离交换可能跨过相等元素;