排序算法2-选择排序

选择排序

• 平均时间复杂度:O(n^2)
• 最好情况:O(n^2)
• 最坏情况:O(n^2)
• 空间复杂度:O(1)
• 排序方式:In-place
• 稳定性:不稳定

算法步骤:
1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3.重复第二步，直到所有元素均排序完毕。

function selectionSort(arr) {
  let len = arr.length;
  let minV, temp;
  for (let i = 0; i < len - 1; i++) {
    minV = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minV]) {
        minV = j;
      }
    }
    temp = arr[minV];
    arr[minV] = arr[i];
    arr[i] = temp;
  }
}

改进
优化1 每次找出最小值的同时找出最大值

function selectionSort(arr) {
  let left = 0,
    right = arr.length - 1;
  let minV, maxV, temp;
  while (left < right) {
    minV = left;
    maxV = right;
    for (let j = left + 1; j < right; j++) {
      if (arr[j] < arr[minV]) {
        minV = j;
      }
      if (arr[j] > arr[maxV]) {
        maxV = j;
      }
    }
    temp = arr[minV];
    arr[minV] = arr[left];
    arr[left] = temp;
    left++;

    temp = arr[maxV];
    arr[maxV] = arr[right];
    arr[right] = temp;
    right--;
  }
}