选择排序

思路

上次我们讲了冒泡排序，其实冒泡排序按照正常人的思路还真不一定想出来，大部分人第一种想到的排序肯定是今天我们要讲的选择排序，这个排序的思路很简单，我们假设第一个数是最小的，再遍历剩余的数如果剩余的数中有一个数比当前数还小那么我们就把当前这个数的下标记录下来，直到所有剩余的数都遍历完毕，这个时候我们可以交换第一个数和最小的那个数，此时数组的第一个数就是最小的，这个时候我们对剩余的数做重复操作即可，还有一个办法就是选择最大的数往后面放，思路是一样的我就不多说了，这个排序方法大家都会，不会也没关心，看下面的演示图：

这个动画中每次选择最小的一个数放到最前面，废话少说，直接上代码。

/**
 *
 * @param {number[]} arr - 需要排序的数组
 * @description 普通的选择排序
 */
export function selectSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    let minIndex = i;
    for (let j = i + 1; j < len; j++) { // 找到本轮最小的值
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    swap(arr, i, minIndex); // 交换最小值和选择值的下标
  }
}

思考

之前我们在讲冒泡排序的时候讲过一个两边同时排序的思想，并且把它称之为鸡尾酒排序，现在我们把这种思想应用到选择排序里面来，我们可以定义两个指针分别为left和right，初始值分别为0和length-1，left从左往右边找小于自己的数，right从右往左别找大于自己的数，同时定义两个变量来保存本轮的最小值和最大值的下标，minIndex和maxIndex默认为left和right相同的下标，在每一轮循环的末尾对left和minIndex以及right和maxIndex做交换，这个时候首位分别为最小值和最大值，我们只需对中间剩余的数做相同的操作就可以了，当left>right时我们结束外层循环即可。⚠️这里面有一个坑，不注意很难想到，假设我们有下面这样一个数组[99,8,2,33,4],当第一轮循环结束时maxIndex指向left,minIndex指向2，我们会交换最小值和left，交换之后原本maxIndex指向的99变成了2，这个时候我们再将2和4交换位置显然错了，因为最小值交换之后minIndex指向了最大值，这个时候我们要把minIndex赋值给maxIndex。所以要在最小值交换之后，以及最大值交换之前做一个判断，当left===maxIndex的话，那么maxIndex=minIndex。

/**
 *
 * @param {number[]} arr
 * @description 两端同时排序，类似鸡尾酒排序
 */
export function selectSort2(arr) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    let minIndex = left;
    let maxIndex = right;

    for (let i = left; i <= right; i++) {
      // 寻找最小值的索引
      if (arr[i] < arr[minIndex]) {
        minIndex = i;
      }
      // 寻找最大值的索引
      if (arr[i] > arr[maxIndex]) {
        maxIndex = i;
      }
    }

    // 将最小值交换到左边
    [arr[left], arr[minIndex]] = [arr[minIndex], arr[left]];
    // 如果最大值的索引是左边的索引，由于left和minIndex交换，这个时候maxIndex会指向交换后的值
    if (maxIndex === left) {
      maxIndex = minIndex;
    }
    // 将最大值交换到右边
    [arr[right], arr[maxIndex]] = [arr[maxIndex], arr[right]];

    // 更新左右指针
    left++;
    right--;
  }
}

总结

选择排序是一种十分直观的排序，也是大部分人能想到的排序，如果我早生30年说不定这个排序就以我的名字命名了😂，对于后面这种两边排序的思想作一种思路即可，在测试之后你会发现速度也就那样，有时候比普通的选择排序还慢，所以只需掌握第一种即可。