建设性插入排序

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

反向问题出现在插入函数的 foror 循环中，当您的循环达到这些值时，它会启动反向模式def insert(B, k, hi, A):&nbsp; &nbsp; # when hi=5&nbsp; &nbsp; for x in range(hi-1, -1, -1):&nbsp; &nbsp; &nbsp; &nbsp; # x = 4&nbsp; &nbsp; &nbsp; &nbsp; # here B[4] is 10 and k=1 so B[4] <= 1 is False&nbsp; &nbsp; &nbsp; &nbsp; # you program does not execute the inside of if&nbsp; &nbsp; &nbsp; &nbsp; # instead it jumps to B = append(B, A[x]) where A[4] == 10&nbsp; &nbsp; &nbsp; &nbsp; # and the this loop goes in reverse mode from 4 to 0&nbsp; &nbsp; &nbsp; &nbsp; # when x = 3&nbsp; &nbsp; &nbsp; &nbsp; # B[x] = 8 so 8 is not less or equal of k where k = 1&nbsp; &nbsp; &nbsp; &nbsp; # so it jumps again to B = append(B, A[x]) where A[x] = A[3] = 8&nbsp; &nbsp; &nbsp; &nbsp; # so it append 8&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # and so on&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # when this loop is finished your list will look like [1,4,6,8,10,10,8,6,4,2]&nbsp; &nbsp; &nbsp; &nbsp; # the 1 gets added when the loop is finished at B[0] = k&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # and then rest of the outputs are result of the loop inside the insertionSort func&nbsp; &nbsp; &nbsp; &nbsp; if B[x] <= k:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; B = append(B, k)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return B&nbsp; &nbsp; &nbsp; &nbsp; B = append(B, A[x])&nbsp; &nbsp; B[0] = k&nbsp;&nbsp; &nbsp; return B这是一个解决方案：def insertionSort(A):&nbsp; &nbsp; copy_sort = A.copy()&nbsp; &nbsp; for i in range(1, len(copy_sort)):&nbsp; &nbsp; &nbsp; &nbsp; item = copy_sort[i]&nbsp; &nbsp; &nbsp; &nbsp; j = i - 1&nbsp; &nbsp; &nbsp; &nbsp; while j >= 0 and copy_sort[j] > item:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; copy_sort[j + 1] = copy_sort[j]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j -= 1&nbsp; &nbsp; &nbsp; &nbsp; copy_sort[j + 1] = item&nbsp; &nbsp; return copy_sortyour_array = [2,4,6,8,10,1,3,5,7,9]sorted = insertionSort(your_array)print(your_array)print(sorted)

Answer 2

您需要在纸上制定算法，然后将这些步骤转换为 Python 代码。您实施的内容令人费解且不正确。最重要的insert是，对于它需要的信息以及它应该如何完成它的工作感到非常困惑。从您的代码中我可以看出，您希望此例程将给定值k插入到 list 中的适当位置B。出于某种原因，您还传入了列表A和该列表中的值的位置，这两者都不适用。你的日常工作很奇怪。从末尾开始B（使用i而不是B自身），代码检查 B 的元素；每次在列表中找到一个小于新值的值时，它都会将新值附加到B.&nbsp;无论进行何种比较，它都会附加Ato的相应元素B。您没有将元素插入到正确的位置。重写这段代码。从最少的必要信息开始：def&nbsp;insert(arr,&nbsp;new_val): #&nbsp;insert&nbsp;new_val&nbsp;into&nbsp;the&nbsp;list&nbsp;arr现在，您的函数需要执行两个步骤：找到合适的位置new_val使用插入该位置的值创建一个新列表。你返回那个新列表。你能从那里继续吗？