选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n^2) 时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。

算法步骤

1. 首先在未排序的序列中预定义最小值对应的索引变量，通常是第 i 轮循环对应元素的索引号。
2. 然后在本轮循环中逐一对比，如果有更小的值则更新索引变量，循环结束交换两个索引对应的值。
3. 重复第二步，直到所有元素均排序完毕。

代码实现

基本思想：每轮循环两两比较，得出一个最值对应的索引，最后根据索引交换元素。

function selectionSort(nums) {
  let minIndex;

  for (let i = 0; i < nums.length - 1; i++) {
    minIndex = i;

    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[minIndex]) {
        minIndex = j; // 更新最小元素对应的索引
      }
    }

    if (minIndex !== i) {
      swap(nums, i, minIndex);
    }
  }

  return nums;
}

复杂度分析

空间复杂度：在整个排序的过程中，我们是直接在原数组内进行元素的两两交换，所以空间复杂度是 O(1)。

时间复杂度：不论什么数据，时间复杂度都是 O(n^2)。