My doc

主题

选择排序 ​

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

算法原理 ​

选择排序的主要思想是：

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

JavaScript 实现 ​

js
/**
 * 选择排序实现
 * @param {Array} array - 待排序的数组
 * @returns {Array} 排序后的新数组
 */
function selectionSort(array) {
  // 创建数组副本以避免修改原数组
  const sorted = [...array];
  const len = sorted.length;
  
  // 遍历数组的每个位置
  for (let i = 0; i < len - 1; i++) {
    // 假设当前位置为最小值的位置
    let minIndex = i;
    
    // 在未排序部分寻找最小值
    for (let j = i + 1; j < len; j++) {
      if (sorted[j] < sorted[minIndex]) {
        minIndex = j; // 更新最小值索引
      }
    }
    
    // 如果最小值不是当前位置，则交换
    if (minIndex !== i) {
      [sorted[i], sorted[minIndex]] = [sorted[minIndex], sorted[i]];
    }
  }
  
  return sorted;
}

// 使用示例
const numbers = [64, 34, 25, 12, 22, 11, 90];
const sortedNumbers = selectionSort(numbers);
console.log('原数组:', numbers);
console.log('排序后:', sortedNumbers);

算法特点 ​

  • 时间复杂度:
    • 最坏情况: O(n²)
    • 最好情况: O(n²)
    • 平均情况: O(n²)
  • 空间复杂度: O(1) (原地排序)
  • 稳定性: 不稳定排序 (相等元素的相对位置可能会改变)
  • 适应性: 不是适应性排序算法，无论输入数据如何，时间复杂度始终是O(n²)

优缺点 ​

优点 ​

  1. 实现简单，代码简洁
  2. 是原地排序算法，空间复杂度低
  3. 交换次数少，最多进行n-1次交换
  4. 对于小规模数据排序效率尚可

缺点 ​

  1. 时间复杂度固定为O(n²)，即使是已排序的数据也需要相同时间
  2. 不是稳定排序算法
  3. 对于大规模数据排序效率低

应用场景 ​

  1. 教学演示排序算法原理
  2. 小规模数据排序
  3. 内存写操作成本较高的场景（因为交换次数少）
  4. 对稳定性无要求的排序场景

选择排序虽然效率不高，但由于其实现简单且交换次数少，在某些特定场景下仍有应用价值。