求助：从末尾索引开始的升序Insertion Sort（Python）实现及代码修正

需求说明 #

给定数组 A = [5,4,3,2,6]，要求使用插入排序算法从最后一个索引开始进行升序排序，最终得到有序数组 [2,3,4,5,6]。迭代过程示例如下：

• 迭代1：A=[5,4,3,2,6]（初始状态，最后一个元素6已有序）
• 迭代2：A=[5,4,2,3,6]
• 迭代3：A=[5,2,3,4,6]
• 迭代4：A=[2,3,4,5,6]（排序完成）

原代码问题分析 #

你提供的代码存在以下几个关键问题：

for j in range(len(arr), j>0):
    value_to_sort = arr[j]
    while arr[j-1] > value_to_sort and j>0:
        arr[j], arr[j-1] = arr[j-1], arr[j]
        i = i+1
return arr

1. range函数语法错误：Python的range参数格式为range(start, stop[, step])，你写的range(len(arr), j>0)完全不符合语法规范，无法生成正确的遍历序列。
2. 未定义变量i：代码中直接使用i = i+1，但i从未初始化，会抛出NameError。
3. 内层循环逻辑错误：交换元素后未更新j的值，会导致死循环；同时j>0的判断应该放在数组访问之前，避免索引越界。

修正后的代码 #

以下是符合需求的插入排序实现（交换版，匹配你的迭代示例）：

def insertion_sort_swap_from_end(arr):
    # 从倒数第二个元素开始，向前遍历所有未排序元素
    for j in range(len(arr)-2, -1, -1):
        current_j = j
        # 向右交换，直到当前元素不大于右侧元素
        while current_j < len(arr)-1 and arr[current_j] > arr[current_j+1]:
            arr[current_j], arr[current_j+1] = arr[current_j+1], arr[current_j]
            current_j += 1
    return arr

# 测试
arr = [5,4,3,2,6]
print(insertion_sort_swap_from_end(arr))  # 输出: [2,3,4,5,6]

代码说明 #

• 外层循环：从索引len(arr)-2（对应元素2）开始，以步长-1遍历到索引0，确保每次处理未排序部分的最左侧元素，向右插入到有序区域（右侧）的正确位置。
• 内层循环：将当前元素与右侧已排序区域的元素逐一比较，若当前元素更大，则交换位置并继续向右比较，直到找到合适的位置。

这个版本的迭代过程和你给出的示例完全一致：

• 初始：[5,4,3,2,6]
• j=3（元素2）：交换2和3 → [5,4,2,3,6]
• j=2（元素4）：交换4和2 → [5,2,4,3,6]，再交换4和3 → [5,2,3,4,6]
• j=1（元素5）：交换5和2 → [2,5,3,4,6]，交换5和3 → [2,3,5,4,6]，交换5和4 → [2,3,4,5,6]

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