递归实现Insertion Sort时数组最后一个元素未参与排序问题求助

• 你代码里的mylist = mylist[:len(mylist)-1]切片操作会生成全新的数组对象，后续递归和插入操作修改的都是这个新对象，完全不会影响外层传入的原始数组，原始数组的最后一位永远不会被触及。
• 递归逻辑设计错误：递归插入排序的核心逻辑是「先排序前n-1个元素，再把第n个元素插入到前n-1个已排序序列的合适位置」，但你现在直接切掉了最后一位丢弃处理，根本没有把最后一位元素纳入插入流程。

我们改用传递下标边界的方式直接操作原始数组，避免生成新对象：

from array import *
mylist = array('i',[5,4,3,2,1,0])

def insertionsort(mylist, n=None):
    # 初始化n为数组长度
    if n is None:
        n = len(mylist)
    # 基线条件：只剩1个元素无需排序
    if n <= 1:
        return
    # 先排序前n-1个元素
    insertionsort(mylist, n-1)
    # 把第n个元素（下标n-1）插入到前面已排序序列的合适位置
    key = mylist[n-1]
    j = n - 2
    while j >= 0 and key < mylist[j]:
        mylist[j+1] = mylist[j]
        j -= 1
    mylist[j+1] = key

insertionsort(mylist)
print(mylist)

运行后输出为array('i', [0, 1, 2, 3, 4, 5])，符合预期。

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