# 插入排序

# 算法原理

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

# 算法步骤

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

# 动图演示

比较次数: 0

交换次数: 0

# 代码实现

function insertionSort(arr) {
  const len = arr.length;
  
  for (let i = 1; i < len; i++) {
    const current = arr[i];
    let j = i - 1;
    
    // 寻找插入位置并移动元素
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    
    // 插入元素
    arr[j + 1] = current;
  }
  
  return arr;
}

# 复杂度分析

# 时间复杂度

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

# 空间复杂度

O(1)，只需要一个临时变量用于存储当前插入的元素

# 算法特点

# 优点

实现简单，容易理解
稳定排序
原地排序，不需要额外空间
对于小规模数据或基本有序的数据效率较高
可以用作在线算法，即可以一边输入数据，一边进行排序

# 缺点

对于大规模数据排序效率较低
每次只能将数据移动一位

# 适用场景

小规模数据排序
数据基本有序的情况
需要稳定排序的场景
在线排序场景

# 优化方案

二分查找优化：使用二分查找来快速找到插入位置
Shell排序：插入排序的改进版本，通过比较相距一定间隔的元素来提高效率

function optimizedInsertionSort(arr) {
  const len = arr.length;
  
  // 使用二分查找优化查找插入位置
  function binarySearch(arr, target, start, end) {
    while (start <= end) {
      const mid = Math.floor((start + end) / 2);
      if (arr[mid] === target) return mid + 1;
      if (arr[mid] < target) start = mid + 1;
      else end = mid - 1;
    }
    return start;
  }
  
  for (let i = 1; i < len; i++) {
    const current = arr[i];
    const j = i - 1;
    
    // 使用二分查找找到插入位置
    const pos = binarySearch(arr, current, 0, j);
    
    // 移动元素
    for (let k = j; k >= pos; k--) {
      arr[k + 1] = arr[k];
    }
    
    // 插入元素
    arr[pos] = current;
  }
  
  return arr;
}

← 选择排序归并排序 →