排序算法 INSERTION SORT
插入排序.
逐个将新元素插入左侧有序区间。
时间平均 O(n²) / 最好 O(n)额外空间O(1)稳定性稳定
原理与执行逻辑
维护一个有序前缀，将右侧的新元素逐个插入前缀的合适位置。当前实现通过连续的相邻交换让新元素向左移动。
执行步骤
- 从下标 1 开始，左边单个元素构成初始有序前缀。
- 将当前元素与左侧相邻元素比较。
- 左侧值更大时交换并继续左移，直到左侧不大于当前值或到达开头。
- 处理下一个元素，直到整个数组有序。
关键理解
插入完成后，a[0..i] 有序，但其中元素还可能在后续插入时移动。仅在严格大于时交换，保证稳定性。
简短示例
[2, 5, 3] 的前两个元素已有序；3 与 5 交换，再与 2 比较后停止，得到 [2, 3, 5]。
代码与执行动画
STEP 0 / 42function insertionSort(arr) { for (let i = 1; i < arr.length; i++) { let j = i; while (j > 0 && arr[j - 1] > arr[j]) { [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]]; j--; } } return arr;}高亮对应当前步骤；源码对传入数组进行原地排序。
数组状态
升序 · 8 个元素比较 0实际交换 0数组写入 0当前区间 —
待排序当前操作已就位
下标显示在底部；柱体随元素移动，等值元素也保留独立身份。
0
准备排序
点击下一步或自动播放，观察数组从左到右升序排列的过程。
调整待排序数组
使用相同数据切换算法，观察比较与交换过程。
插入排序的执行规则
本实现通过相邻交换插入元素。左侧有序前缀仍可能移动，全部完成后才标记最终位置。
交换次数仅统计两个不同位置的交换；可输入重复值。对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
将插入排序迁移到链表，通过修改指针完成插入。