用Python可视化MergeSort

Question

我想在蟒蛇里做一个合并视觉化器。我想用海龟模块。要绘制单个条形图，我使用函数draw_bar，而要绘制整个数组，则需要函数draw_bars。这是代码

def draw_bar(x,y,w,h):
    turtle.up()
    turtle.goto(x,y)
    turtle.seth(0)
    turtle.down()
    turtle.begin_fill()
    turtle.fd(w)
    turtle.left(90)
    turtle.fd(h)
    turtle.left(90)
    turtle.fd(w)
    turtle.left(90)
    turtle.fd(h)
    turtle.left(90)
    turtle.end_fill()

def draw_bars(v,currenti=-1,currentj=-1,M=500):
    turtle.clear()
    x = -250
    n = len(v)
    w = 500/n
    r = 500/M
    for  i in range(n):
        if i == currenti: turtle.fillcolor('red')
        elif i == currentj: turtle.fillcolor('blue')
        else: turtle.fillcolor('gray')
        draw_bar(x,-250,w,v[i]*r)
        x += w
    screen.update()

现在我有了这个合并排序算法：

def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]
        mergeSort(L)
        mergeSort(R)
        i=0
        j=0
        k=0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

现在，我需要知道ho将刷新可视化列表的代码部分。

Answer 1

每次更改数组时，都需要更新grafics，这意味着在每个arr[k] = L[j]之后

然而，在当前的实现中很难做到这一点，因为递归函数没有关于它正在操作的更大列表的哪一部分的信息。

我建议更改这个函数，以便它总是被传递给compleat数组，以及它将要处理的部分的开始索引和长度：

def mergeSort(arr, start, length):
    if length > 1:
        mergeSort(arr, start, length/2)
        mergeSort(arr, start+length/2, length/2)
        etc.

然后，您将能够每次调用drawbars时，您的数组都会发生变化。

编辑：

完整的代码如下所示：

def mergeSort(arr, start, length):
    if length > 2:
        mergeSort(arr, start, int(length/2))
        mergeSort(arr, start+int(length/2), int(length/2))
    
    print(start+int(length/2))
    L = arr[start:start+int(length/2)]
    R = arr[start+int(length/2):start+length]
    i=0
    j=0
    k=0
    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            arr[start+k] = L[i]
            draw_bars(myarray)
            i += 1
        else:
            arr[start+k] = R[j]
            draw_bars(myarray)
            j += 1
        k += 1
    while i < len(L):
        arr[start+k] = L[i]
        draw_bars(myarray)
        i += 1
        k += 1
    while j < len(R):
        arr[start+k] = R[j]
        draw_bars(myarray)
        j += 1
        k += 1
        
myarr = [2,345,2456,3456,56,34,5,78,34,5423,26487,324,1,3,4,5]
draw_bars(myarray)
mergeSort(myarr, 0 ,len(myarr))
print(myarr)