手写选择排序算法

问题

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

需要实现一个选择排序函数，能够对数组进行升序排序。

解答

/**
 * 选择排序
 * @param {number[]} arr - 待排序的数组
 * @return {number[]} - 排序后的数组
 */
function selectionSort(arr) {
  // 创建数组副本，避免修改原数组
  const result = [...arr];
  const len = result.length;
  
  // 外层循环：控制已排序区间的边界
  for (let i = 0; i < len - 1; i++) {
    // 假设当前位置是最小值的索引
    let minIndex = i;
    
    // 内层循环：在未排序区间中找到最小值的索引
    for (let j = i + 1; j < len; j++) {
      if (result[j] < result[minIndex]) {
        minIndex = j;
      }
    }
    
    // 如果最小值不是当前位置，则交换
    if (minIndex !== i) {
      [result[i], result[minIndex]] = [result[minIndex], result[i]];
    }
  }
  
  return result;
}

/**
 * 选择排序（降序版本）
 * @param {number[]} arr - 待排序的数组
 * @return {number[]} - 排序后的数组
 */
function selectionSortDesc(arr) {
  const result = [...arr];
  const len = result.length;
  
  for (let i = 0; i < len - 1; i++) {
    let maxIndex = i;
    
    for (let j = i + 1; j < len; j++) {
      if (result[j] > result[maxIndex]) {
        maxIndex = j;
      }
    }
    
    if (maxIndex !== i) {
      [result[i], result[maxIndex]] = [result[maxIndex], result[i]];
    }
  }
  
  return result;
}

使用示例

// 示例1：基本使用
const arr1 = [64, 25, 12, 22, 11];
console.log('原数组:', arr1);
console.log('升序排序:', selectionSort(arr1));
// 输出: [11, 12, 22, 25, 64]

// 示例2：降序排序
const arr2 = [5, 2, 8, 1, 9];
console.log('降序排序:', selectionSortDesc(arr2));
// 输出: [9, 8, 5, 2, 1]

// 示例3：包含重复元素
const arr3 = [3, 1, 4, 1, 5, 9, 2, 6];
console.log('排序结果:', selectionSort(arr3));
// 输出: [1, 1, 2, 3, 4, 5, 6, 9]

// 示例4：已排序数组
const arr4 = [1, 2, 3, 4, 5];
console.log('已排序数组:', selectionSort(arr4));
// 输出: [1, 2, 3, 4, 5]

// 示例5：单个元素
const arr5 = [42];
console.log('单元素数组:', selectionSort(arr5));
// 输出: [42]

// 示例6：空数组
const arr6 = [];
console.log('空数组:', selectionSort(arr6));
// 输出: []

关键点

• 思想：每次从未排序区间中选择最小（或最大）的元素，放到已排序区间的末尾

• 双层循环结构：

  • 外层循环控制已排序区间的边界（i 从 0 到 n-2）
  • 内层循环在未排序区间中查找最小值（j 从 i+1 到 n-1）

• 原地排序：只需要常数级的额外空间，通过交换元素位置完成排序

• 时间复杂度：

  • 最好情况：O(n²)
  • 平均情况：O(n²)
  • 最坏情况：O(n²)
  • 无论数据初始状态如何，都需要进行完整的比较

• 空间复杂度：O(1)，只需要一个临时变量用于交换

• 稳定性：选择排序是不稳定的排序算法，因为交换操作可能改变相同元素的相对位置

• 优化技巧：可以同时找出最小值和最大值，分别放到序列两端，减少遍历次数

• 适用场景：数据规模较小、对稳定性无要求的场景；由于交换次数少（最多 n-1 次），在交换操作代价较大时有优势