手写插入排序算法

问题

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

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

解答

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

/**
 * 原地插入排序（直接修改原数组）
 * @param {number[]} arr - 待排序的数组
 * @return {number[]} - 排序后的数组
 */
function insertionSortInPlace(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;
}

/**
 * 支持自定义比较函数的插入排序
 * @param {Array} arr - 待排序的数组
 * @param {Function} compareFn - 比较函数
 * @return {Array} - 排序后的数组
 */
function insertionSortWithCompare(arr, compareFn = (a, b) => a - b) {
  const result = [...arr];
  const len = result.length;
  
  for (let i = 1; i < len; i++) {
    const current = result[i];
    let j = i - 1;
    
    // 使用自定义比较函数
    while (j >= 0 && compareFn(result[j], current) > 0) {
      result[j + 1] = result[j];
      j--;
    }
    
    result[j + 1] = current;
  }
  
  return result;
}

使用示例

// 示例1：基本使用
const arr1 = [5, 2, 8, 1, 9, 3];
console.log(insertionSort(arr1)); 
// 输出: [1, 2, 3, 5, 8, 9]

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

// 示例3：逆序数组
const arr3 = [5, 4, 3, 2, 1];
console.log(insertionSort(arr3)); 
// 输出: [1, 2, 3, 4, 5]

// 示例4：包含重复元素
const arr4 = [3, 1, 4, 1, 5, 9, 2, 6];
console.log(insertionSort(arr4)); 
// 输出: [1, 1, 2, 3, 4, 5, 6, 9]

// 示例5：降序排序
const arr5 = [5, 2, 8, 1, 9];
console.log(insertionSortWithCompare(arr5, (a, b) => b - a)); 
// 输出: [9, 8, 5, 2, 1]

// 示例6：对象数组排序
const students = [
  { name: 'Alice', score: 85 },
  { name: 'Bob', score: 92 },
  { name: 'Charlie', score: 78 }
];
console.log(insertionSortWithCompare(students, (a, b) => a.score - b.score));
// 输出: [{ name: 'Charlie', score: 78 }, { name: 'Alice', score: 85 }, { name: 'Bob', score: 92 }]

// 示例7：原地排序
const arr6 = [3, 1, 4, 1, 5];
insertionSortInPlace(arr6);
console.log(arr6); 
// 输出: [1, 1, 3, 4, 5]（原数组被修改）

关键点

• 思想：将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的正确位置

• 双层循环：外层循环遍历未排序元素，内层循环在已排序序列中找到插入位置

• 元素移动：通过 while 循环将大于当前元素的已排序元素依次后移，为插入腾出空间

• 时间复杂度：

  • 最好情况：O(n) - 数组已排序，只需遍历一次
  • 平均情况：O(n²)
  • 最坏情况：O(n²) - 数组逆序

• 空间复杂度：O(1) - 只需要常数级额外空间

• 稳定性：插入排序是稳定的排序算法，相等元素的相对位置不会改变

• 适用场景：

  • 数据量较小的情况
  • 数组基本有序的情况
  • 需要稳定排序的场景
  • 在线排序（可以边接收数据边排序）

• 优化技巧：可以使用二分查找优化查找插入位置的过程，但整体时间复杂度仍为 O(n²)