选择排序的基本实现

笔记整理自 coderwhy 『TypeScript 高阶数据结构与算法』课程

概念

• 本质：两两元素相比较，先扫描一遍未排序数列，把未排序的数列中的最小(大)元素，放到数列的已排序的末尾

特性

• 选择排序是冒泡排序的优化版本，主要优化了交换的过程
• 在所有完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种

复杂度分析

• 时间复杂度：
  • 最好情况：O(n^2)
  • 最坏情况：O(n^2)
  • 平均情况：O(n^2)
• 空间复杂度：O(1)，原地排序

使用场景

时间复杂度较高为 O(n^2)

• 适用于小数据量
• 不适用于大数据量

具体代码

/**
 - @desc  : 选择排序实现
 */
function selectionSort(arr: number[]): number[] {
  // 需扫描，则要使用到数组长度
  const n = arr.length;

  // 数组中有多少个需要扫描的元素
  // 为何 n - 1，因为前面的元素都扫描了，最后一个元素不需再扫描
  for (let i = 0; i < n - 1; i++) {
    // 获取最小值的索引，始终以已排序的末尾索引，作为 minIndex
    let minIndex = i;

    // 每个元素需要扫描的次数
    // 为何从 1 开始；因为 minIndex 从 0 开始的，索引 0 和 0 比较，即为自己和自己比较，无意义
    // 为何 j = 1 + i；因为每扫描一次之后，已排序的末尾索引是跟随 i 变化的
    for (let j = 1 + i; j < n; j++) {
      // 找到更小的数据，则更新 minIndex
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // 当前位置已经是未排序数列中最小的数值，则不需交换，是个小优化点
    if (i !== minIndex) {
      [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
    }
  }

  return arr;
}

// 算法测试
let arr = [10, 90, 20, 100, 50];
console.log('排序前：', arr); // [ 10, 90, 20, 100, 50 ]

let newArr = selectionSort(arr);
console.log('排序后：', newArr); // [ 10, 20, 50, 90, 100 ]