Python中的Mergesort实现 [英] Mergesort implementation in Python

问题描述

我一直在Python/C ++中实现一个mergesort(来自Interactivepython).该代码完全可以工作，但是我的问题是我似乎无法弄清楚为什么代码的特定部分实际上可以工作.

I've been implementing a mergesort (from interactivepython) in Python/C++. The code fully works, but my issue is that I can't seem to figure out why a particular portion of the code actually does work.

代码是:

def mergeSort(alist):
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i]<righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i<len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j<len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1

plist = [54,26,93,17]
mergeSort(plist)
print(plist)

在lefthalf = [54 26]之后，进一步的子例程拆分为lefthalf = [54]和righthalf = [26]，合并代码将提供alist = [26，54](这是排序后的左半部分).

After lefthalf = [54 26], the further subroutine split to lefthalf = [54] and righthalf = [26], the merge code works to provide alist = [26, 54] (which is the sorted left half).

现在，在调试窗口中进行下一步，我得到lefthalf = [26，54].这是怎么可能的，因为第一次调试显示之前将其定义为[54，26].更新到[26，54]在哪里发生?

Now the next step that I do in the debug window, I get a lefthalf = [26, 54]. How is this possible, as the first debug shows it defined as [54, 26] before. Where does the update to [26, 54] happen?

任何帮助将不胜感激！

推荐答案

您的mergesort函数修改就位传递给它的列表.也就是说，它会更改内容，以便项目按顺序排列，而不是返回新列表.

Your mergesort function modifies the list you pass to it in place. That is, it changes the contents so that the items are in order, rather than returning a new list.

这是您在递归调用期间在调试器中看到的内容.在递归的第一级中，通过复制原始列表中的某些值(使用切片语法)来创建lefthalf.它开始包含[54, 26].然后，此列表传递给另一个mergesort调用.请注意，命名可能会造成混淆，因为在内部调用中，其将列表称为alist(并且具有自己的单独的lefthalf列表).当内部调用返回时，外部调用的lefthalf的内容原来已被修改为[26, 54](它们是有序的，这就是我们想要的！).

This is what you're seeing in your debugger, during the recursive calls. In the first level of the recursion, lefthalf is created by copying some values from the original list (with slice syntax). It starts out containing [54, 26]. This list is then passed to another call of mergesort. Note that the naming can get confusing, as in the inner call it refers to the list as alist (and it has its own separate lefthalf list). When the inner call returns, the contents of the outer call's lefthalf turn out to have been modified to [26, 54] (they're in order, which is what we want!).

可能是您的调试器没有在返回发生时弄清楚.由于它们都是相同的功能(由于递归)，所以当内部调用结束并且外部调用的控制流恢复时，它可能并不明显.

It may be that your debugger isn't making it clear when the return is happening. Since it's all the same function (due to the recursion), it may not be obvious when the inner call ends and the control flow of the outer call resumes.

这是您的代码的演练，其中在对示例列表进行排序时，我在递归的各个级别中显示了不同变量的值.请注意，这不是可运行的Python代码，我只是为了表示递归级别，而不是为了控制流.为了使示例相对简短，我还省略了一些步骤，例如比较两个子列表中的值以及在合并过程中更新i j和k索引:

Here's a walkthrough of your code in which I show the the values of the the different variables in the various levels of the recursion as you sort your example list. Note that this isn't runnable Python code, I'm indenting to indicate the level of recursion, not for control flow. To keep the example relatively short, I'm also leaving out some steps such as as comparing the values from the two sublists and updating the i j and k indexes during the merge process:

plist = [54,26,93,17]
mergesort(plist)
    # alist is a referece to plist which contains [54,26,93,17]
    lefthalf = alist[:mid]  # new list which initially contains [54,26]
    righthalf = alist[mid:] # new list which initially contains [93,17]
    mergesort(lefthalf)
        # alist is a reference to the outer lefthalf list, which contains [54,26]
        lefthalf = alist[:mid]  # new list, initially contains [54]
        righthalf = alist[mid:] # new list, initially contains [26]
        mergesort(lefthalf)
            # alist is a reference to the previous level's lefthalf, [54]
            # the if statement doesn't pass its test, so we do nothing here (base case)
        # lefthalf was not changed by the recursive call
        mergesort(righthalf)
            # alist is a reference to the previous level's righthalf, [26]
            # base case again
        # righthalf was not changed
        alist[k]=righthalf[j] # now we merge lefthalf and righthalf back into alist
        alist[k]=lefthalf[i] # these statements change the contents of alist
    # lefthalf's contents changed, it is now sorted, [26,54]
    mergesort(righthalf)
        # alist is a reference to the outer righthalf list, which contains [93,17]
        lefthalf = alist[:mid]  # new list, initially contains [93]
        righthalf = alist[mid:] # new list, initially contains [17]
        mergesort(lefthalf) # base case, nothing happens (I'll skip the details)
        mergesort(righthalf) # base case, nothing happens
        alist[k]=righthalf[j] # merge lefthalf and righthalf back into alist
        alist[k]=lefthalf[i]  # we change the contents of alist to [17,93]
    # righthalf's contents changed, it is now sorted, [17,93]
    alist[k]=righthalf[j] # merge lefthalf and righthalf back into alist (more steps)
    alist[k]=lefthalf[i]
    alist[k]=lefthalf[i]
    alist[k]=righthalf[j] # after these statements, alist is [17,26,54,93]
# plists's contents are changed so it contains [17,26,54,93]

这可能会帮助您从这种复杂的递归情况中退后一步，并查看一个更简单的示例以确保您了解如何对列表进行突变:

It might help you to step back a bit from this complex recursive situation and look at a simpler example to make sure you understand how lists can be mutated:

a = [1, 2] # create a list object with some initial contents

b = a      # b refers to the same list object as a, nothing is copied
b[1] = 3   # this modifies the list object itself, replacing the 2 with a 3

print(a)   # prints [1, 3] even through we're looking at a rather than b

def func(lst): # lst will be a new name bound to whatever is passed to the function
    lst[1] = 4 # we can modify that passed-in object (assuming it's the right type)

func(a)    # lst in the function will become another name for the list object
print(a)   # prints [1, 4]

这篇关于Python中的Mergesort实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！