02选择排序

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

选择排序算法步骤：

1. 首先在未排序序列中找到最小元素，与第一个元素进行交换，让最小的元素在排序最前面。
2. 再从剩余未排序n-1个元素中继续寻找最小元素，然后与第二个元素交换位置。
3. 重复第二步，第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。

以下面5个无序的数据为例：
56 12 80 91 20（文中仅细化了第一趟的选择过程）

• 第1趟：12 56 80 91 20

  
  第一趟对比过程.png
• 第2趟：12 20 80 91 56
• 第3趟：12 20 56 91 80
• 第4趟：12 20 56 80 91

let arr = [56, 12, 80, 91, 20];

function selectSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[i]) {
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
      }
    }
    console.log(arr)
  }
  return arr;
}

console.log(selectSort(arr)) // [ 12, 20, 56, 80, 91 ]

平均时间复杂度：O(n2)
空间复杂度：O(1) (用于交换和记录索引)
稳定性：不稳定 （比如序列【5， 5， 3】第一趟就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）

排序前：56,12,80,91,20
排序中!!调整：12,56,80,91,20
排序中!!不调整：12,56,80,91,20
排序中!!不调整：12,56,80,91,20
排序中!!不调整：12,56,80,91,20
排序后：12,56,80,91,20
-------------------
排序前：12,56,80,91,20
排序中!!不调整：12,56,80,91,20
排序中!!不调整：12,56,80,91,20
排序中!!调整：12,20,80,91,56
排序后：12,20,80,91,56
-------------------
排序前：12,20,80,91,56
排序中!!不调整：12,20,80,91,56
排序中!!调整：12,20,56,91,80
排序后：12,20,56,91,80
-------------------
排序前：12,20,56,91,80
排序中!!调整：12,20,56,80,91
排序后：12,20,56,80,91
-------------------
最终结果:12,20,56,80,91

image.png