实现原理

1. 分区间操作
   初始时，已排序区间仅包含第一个元素，其余元素属于未排序区间。遍历未排序区间的元素时，逐个将其与已排序区间的元素从后向前比较，找到合适的位置插入。

• 示例：若数组为 [5, 3, 8, 1]，初始已排序区间为 [5]，未排序区间为 [3, 8, 1]。处理元素 3 时，将其插入到 5 之前，得到 [3, 5, 8, 1]。

2. 插入方式

• 交换法：通过不断交换相邻元素，将目标元素移动到正确位置。例如在 Java 实现中，使用双重循环比较并交换元素。
• 移动法：先保存目标元素值，将已排序区间中比其大的元素后移，最后将目标元素放入空位。这种方法减少了交换次数，效率更高。
• 代码示例（JavaScript）：

     function insertionSort(arr) {
       for (let i = 1; i < arr.length; 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;
     }

此代码通过移动元素实现插入排序。

复杂度分析

1. 时间复杂度

• 最好情况：数组已完全有序，每次插入只需比较一次，时间复杂度为 O(n) 。
• 最坏/平均情况：数组完全逆序，每个元素需比较并移动所有已排序元素，时间复杂度为 O(n^2) 。

2. 空间复杂度
   插入排序是原地排序算法，仅需常数级额外空间（ O(1) ）。
3. 稳定性
   插入排序是稳定排序，相同元素的相对顺序在排序后保持不变。

应用场景

1. 小规模数据排序
   当数据规模较小时（如 n ≤ 100），插入排序的性能优于复杂度为 O(n log n) 的算法（如快速排序、归并排序），因为其常数因子更小。
2. 部分有序数据
   若数据已接近有序（如日志按时间近似有序），插入排序的时间复杂度接近 O(n)，效率极高。
3. 辅助其他算法
   插入排序常作为高级排序算法（如希尔排序、快速排序）的底层实现，用于处理递归过程中的小规模子数组。
4. 教学与理解基础
   由于其逻辑简单且包含经典的分治思想，插入排序常用于算法教学，帮助理解排序原理。

与其他排序算法的对比

• 冒泡排序：插入排序通过减少交换次数（移动法）优化性能，而冒泡排序需多次交换相邻元素。
• 选择排序：插入排序在部分有序时表现更优，而选择排序无论数据如何都需遍历所有元素。
• 归并排序/快速排序：大规模数据下，插入排序效率低，但可作为这些算法的补充。

总结

插入排序通过逐步构建有序区间的策略实现排序，适用于小规模或部分有序数据，兼具稳定性和空间效率。尽管其时间复杂度较高，但在特定场景下仍是实用且高效的算法。