合并排序未正确发生 - Python

Question

排序不正确。有人可以帮助使用这种方法进行排序吗？也请让我知道我要去哪里错了。我是 Python 的新手，所以我自己做。我正在使用我们在 C 或其他语言中使用的常用方法。

base =[5,4,3,2,1]

def splitarray (low, high):
    if  low < high:
        mid = (high+low)/2

        splitarray (low, mid)
        splitarray (mid+1,high)
        merge(low,mid,high)

    else:
        return

def merge(low,mid,high):
    print("merge " +str(low) + " - " +str(mid)+" - "+ str(high))
    result = [0]*len(base)
    k = 0
    i=low
    j=mid+1
    l=0


    while i <= mid and j <= high:
        if (base[i] < base[j]):

            result[k]= base[i]
            k+=1
            i += 1

        if (base[i] > base[j])  :


            result[k]= base[j]

            j += 1
            k += 1





    while i <= mid:
        result[k]= base[i]
        k += 1
        i += 1
    while j <= high:
        result[k]= base[j]
        #count = count + mid - i
        j += 1
        k += 1

    print result

    l = low
    k= 0
    while l <= high:
        base[l] = result[l]
        l += 1


    print base
splitarray(0,len(base)-1)

Answer 1

视觉上算法的运行方式是：

所以实现归并排序最明显的方法是return每次归并一个新列表。也许可以针对您正在尝试做的事情进行优化，即在单个顶层 result 上运行。但是如果你这样做，你不能只在每个合并级别追加到 result 。因为在递归的底层你会添加四个元素，然后在中间层你会添加四个，然后在顶层你会添加另外四个。太多了。如果你这样做，你应该有一个固定的 result 大小并在整个执行过程中对其索引进行操作。

第二个错误是您正在为每次合并阅读未修改的 base。每个合并步骤的前提是要合并的两个列表已经排序。如果您以明显的方式实现算法，则可以只使用来自更深层次合并的 return 值。如果您使用顶级 result 以某种优化方式实施算法，那么您应该从 result 读取，而不是 base.

Answer 2

您当前（更新的）代码的问题似乎与最后一个循环有关：

l = low
k= 0
while l <= high:
    base[l] = result[l]
    l += 1

在这里，您要将 results 列表中的值复制到 base 列表中。但是，结果都在 results 的开头，而不是您希望它们进入 base 的相同坐标。你似乎 almost 做对了，因为你将 k 设置为零，但你最终没有在循环中使用 k。

尝试：

l = low
k= 0
while l <= high:
    base[l] = result[k]  # read the result from index k, not l
    l += 1
    k += 1  # increment k as well

这应该可以正常工作。请注意，虽然这会正确地进行排序，但这并不是 Python 中非常优雅的排序方式。首先，您只能对一个全局变量 base 进行排序，而不能对任何列表进行排序（将列表作为参数传递会更好）。但是，由于这看起来像是您主要为了学习经验而编写的内容，因此我将进一步改进留给您。

合并排序未正确发生 - Python

Merge Sort not happening correctly - Python

python

mergesort