# 选择排序

# 算法原理

选择排序是一种简单直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

# 算法步骤

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
重复步骤2，直到所有元素均排序完毕

# 动图演示

比较次数: 0

交换次数: 0

# 代码实现

function selectionSort(arr) {
  const len = arr.length;
  
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i;
    
    // 在未排序序列中找到最小值的索引
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    
    // 如果找到的最小值和当前位置不同，则交换
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  
  return arr;
}

# 复杂度分析

# 时间复杂度

最好情况：O(n²)，即使数组已经有序
最坏情况：O(n²)，当数组逆序时
平均情况：O(n²)

# 空间复杂度

O(1)，只需要一个临时变量用于交换

# 算法特点

# 优点

实现简单，容易理解
交换次数较少，对于交换成本较高的场景有优势
原地排序，不需要额外空间

# 缺点

时间复杂度固定为O(n²)，无法优化
不稳定排序
对于大规模数据效率较低

# 适用场景

小规模数据排序
交换成本较高而比较成本较低的场景
对稳定性不敏感的场景

# 优化方案

双向选择排序：每次同时找出最大值和最小值
使用二元选择排序，减少比较次数

function optimizedSelectionSort(arr) {
  const len = arr.length;
  
  for (let i = 0; i < Math.floor(len / 2); i++) {
    let minIndex = i;
    let maxIndex = i;
    
    // 同时寻找最大值和最小值
    for (let j = i + 1; j < len - i; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
      if (arr[j] > arr[maxIndex]) {
        maxIndex = j;
      }
    }
    
    // 放置最小值
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
      // 如果最大值是i，需要更新maxIndex
      if (maxIndex === i) {
        maxIndex = minIndex;
      }
    }
    
    // 放置最大值
    if (maxIndex !== len - 1 - i && maxIndex !== i) {
      [arr[len - 1 - i], arr[maxIndex]] = [arr[maxIndex], arr[len - 1 - i]];
    }
  }
  
  return arr;
}

← 冒泡排序插入排序 →