动画

实现

• 思路
  • 找到数组中的最小值，选中它并将其放置在第一位
  • 接着找到第二小的值，选中它并将其放置在第二位
  • 以此类推执行n-1轮
• 时间复杂度O(n^2)

const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 46, 4, 19, 50, 48];
for (let i = 0; i < arr.length - 1; i++) {
  let indexMin = i; // 每次循环，选中数组第 i 位，临时作为最小值的索引 index
  // 从数组第 i 位开始，找最小值的索引
  for (let j = i; j < arr.length; j++) {
    if (arr[j] < arr[indexMin]) {
      indexMin = j;
    }
  }
  if (i !== indexMin) {
    let tmp = arr[indexMin];
    arr[indexMin] = arr[i];
    arr[i] = tmp;
  }
}
console.log(arr); // [3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

分析

• 第一，选择排序是原地排序算法吗 ？
  选择排序空间复杂度为 O(1)，是一种原地排序算法。
• 第二，选择排序是稳定的排序算法吗 ？
  选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。所以，选择排序是一种不稳定的排序算法。
• 第三，选择排序的时间复杂度是多少 ？
  无论是正序还是逆序，选择排序都会遍历 次来排序，所以，最佳、最差和平均的复杂度是一样的。
  最佳情况：T(n) = O(n^2)。
  最差情况：T(n) = O(n^2)。
  平均情况：T(n) = O(n^2)。