建设性插入排序

Question

我在插入排序时遇到麻烦，我觉得我可能错过了排序的要点，并误解了基本原理。

我们获得了插入排序，该排序可以编辑输入到其中的数组。我们的任务是然后修改我们得到的代码，然后创建将不会编辑原始数组的构造性插入排序]

这是我到目前为止的代码

def append(A, x):
    return A + [x] 

def insertionSort(A):
    B = []
    B = append(B, A[0])
    for i in range(1, len(A)):
        B = insert(B, A[i], i, A)
    return str(B)

def insert(B, k, hi, A):
    print(B, k, hi)
    for x in range(hi-1, -1, -1):
        if B[x] <= k:
            B = append(B, k)
            return B
        B = append(B, A[x])
    B[0] = k 
    return B

print(insertionSort([2,4,6,8,10,1,3,5,7,9]))

但是在列表中的第三个或第四个元素之后，它开始以相反的顺序将所有项目添加到列表的末尾

[2] 4 1
[2, 4] 6 2
[2, 4, 6] 8 3
[2, 4, 6, 8] 10 4
[2, 4, 6, 8, 10] 1 5
[1, 4, 6, 8, 10, 10, 8, 6, 4, 2] 3 6
[1, 4, 6, 8, 10, 10, 8, 6, 4, 2, 1, 10, 8, 6, 4, 3] 5 7
[1, 4, 6, 8, 10, 10, 8, 6, 4, 2, 1, 10, 8, 6, 4, 3, 3, 1, 10, 8, 6, 5] 7 8
[1, 4, 6, 8, 10, 10, 8, 6, 4, 2, 1, 10, 8, 6, 4, 3, 3, 1, 10, 8, 6, 5, 7] 9 9
[1, 4, 6, 8, 10, 10, 8, 6, 4, 2, 1, 10, 8, 6, 4, 3, 3, 1, 10, 8, 6, 5, 7, 9]

我无法绕开为什么这是错误的。

非常感谢任何能提供帮助的人。

Answer 1

您需要在纸上制定算法，然后将这些步骤转换为Python代码。您所实施的是令人费解且不正确的。

最重要的是，insert对于所需的信息及其应如何工作感到非常困惑。从您的代码中可以最好地看出，您希望此例程将给定值k插入列表B中的适当位置。由于某些原因，您还传递了列表A和该值在该列表中的位置，但都不适用。

然后您的例行工作很奇怪；从B的末尾开始（使用i代替B本身），代码检查B的元素；每次在列表中找到小于新值的值时，都会将新值追加到B的末尾。不管进行哪种比较，它都会将A的相应元素附加到B。您没有在适当的地方插入元素。

重写此代码。从最少的必要信息开始：​​

def insert(arr, new_val):
# insert new_val into the list arr

现在，您的功能要执行两个步骤：

• 找到new_val的正确位置
• 创建一个新列表，并在其中插入值。

您返回了该新列表。

您能从那里继续吗？