B2.4.3 · 排序
插入排序 · 拓展
Python · 逐步执行
插入排序 · 拓展
跟随实际的 Python 执行过程，观察列表的变化。
Python 实现
1def insertion_sort(items):2 for i in range(1, len(items)):3 key = items[i]4 j = i - 15 while j >= 0 and items[j] > key:6 items[j + 1] = items[j]7 j = j - 18 items[j + 1] = key9 return items可选拓展，不属于 B2.4.3 指定的两种排序。暂存 key，将较大的值后移；已排序前缀随之增长。最佳情况时间复杂度为 O(n)，最坏为 O(n²)；辅助空间为 O(1)。