插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法原理

插入排序的基本思想是：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

JavaScript 实现

/**
 * 插入排序实现
 * @param {Array} array - 待排序的数组
 * @returns {Array} 排序后的新数组
 */
function insertionSort(array) {
  // 创建数组副本以避免修改原数组
  const sorted = [...array];
  
  // 从第二个元素开始遍历（第一个元素默认已排序）
  for (let i = 1; i < sorted.length; i++) {
    // 当前要插入的元素
    const current = sorted[i];
    // 已排序部分的最后一个元素的索引
    let j = i - 1;
    
    // 在已排序部分从后向前扫描，寻找插入位置
    while (j >= 0 && sorted[j] > current) {
      // 将大于current的元素向后移动一位
      sorted[j + 1] = sorted[j];
      j--;
    }
    
    // 将current插入到正确位置
    sorted[j + 1] = current;
  }
  
  return sorted;
}

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

算法特点

时间复杂度:
- 最坏情况: O(n²) (逆序排列)
- 最好情况: O(n) (已排序)
- 平均情况: O(n²)
空间复杂度: O(1) (原地排序)
稳定性: 稳定排序 (相等元素的相对位置不会改变)
适应性: 是适应性排序算法，对已排序或接近排序的数据效率高

优缺点

优点

实现简单，代码简洁
是稳定排序算法
是原地排序算法
是适应性排序算法，对小规模或基本有序的数据效率很高
在线算法，可以在接收数据的同时进行排序

缺点

时间复杂度较高，大数据集效率低
比较和移动次数较多

应用场景

教学演示排序算法原理
小规模数据排序
数据基本有序的情况下
对稳定性有要求的排序场景
在线排序场景（边接收数据边排序）

插入排序虽然在最坏情况下效率不高，但由于其实现简单且对小规模或基本有序的数据效率很高，在实际应用中经常作为其他高效排序算法的补充。

插入排序 ​

算法原理 ​

JavaScript 实现 ​

算法特点 ​

优缺点 ​

优点 ​

缺点 ​

应用场景 ​

插入排序

算法原理

JavaScript 实现

算法特点

优缺点

优点

缺点

应用场景