思想

原址比较的排序算法。即首先找到数结构中的最小值并将其放置在第一位，然后找到第二小的值将其放置在第二位...以此类推。

代码

function selectionSort(arr) {

  const length = arr.length;

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

    let minIndex = i;

    for (let j = i + 1 ; j < length ; j++) {

      if (arr[j] < arr[minIndex]) {

        minIndex = j;

      }

    }

    if (minIndex !== i) {

      const temp = arr[i];

      arr[i] = arr[minIndex];

      arr[minIndex] = temp;

    }

  }

}

性能分析

• 时间复杂度：最好O(n),平均、最坏O(n^2)
• 空间复杂度: O(1), 不稳定