递归插入排序未完成升序排序，代码中缺失什么？

你的代码核心问题是只完成了当前元素与前一个元素的单次交换，没有将元素向前追溯到已排序序列中的正确位置。插入排序的本质是把当前未排序元素插入到前面已排序数组的合适位置，而不是仅做一次相邻交换。

原代码的执行缺陷 #

以测试用例[3,4,1]为例：

1. 初始调用insertionSort([3,4,1], 1)，arr[1]=4不小于arr[0]=3，直接递归处理idx=2
2. arr[2]=1小于arr[1]=4，交换后数组变为[3,1,4]，接着递归处理idx=3（超出数组长度，返回）
3. 整个过程中，交换后的1没有继续和前面的3比较交换，导致最终结果停留在[3,1,4]

修正后的代码 #

def insertionSort(arr, idx):
    # 向前追溯，将当前元素插入到已排序序列的正确位置
    if idx > 0 and arr[idx] < arr[idx-1]:
        arr[idx], arr[idx-1] = arr[idx-1], arr[idx]
        insertionSort(arr, idx - 1)
    
    # 当前元素到位后，递归处理下一个未排序元素
    if idx < len(arr) - 1:
        insertionSort(arr, idx + 1)
    
    return arr

print(insertionSort([3,4,1], 1))  # 输出: [1,3,4]

修正逻辑说明 #

1. 向前插入阶段：当当前元素比前一个元素小时，交换两者位置，然后递归处理idx-1，继续向前验证，直到元素处于已排序的正确位置（要么到数组开头，要么前一个元素不大于它）
2. 处理下一个元素：当前元素插入完成后，再递归处理idx+1，推进到下一个未排序元素

这样就能完整实现递归版的插入排序，确保每个元素都被插入到正确位置。

内容的提问来源于stack exchange，提问作者kirihadinomoyet