python - 在python类中实现归并排序功能，报错

Question

所以我定义了一个函数，如果它是由它的 lonesome 实现的，那么它非常适合对线性数组进行合并排序，但是如果我把它放到一个类中，它就会出错。我认为这是一个很好的例子，说明我不太了解类(class)的工作原理；可能与命名空间管理有关(？)。

见下文:

def sort(array):
    print('Splitting', array)
    if len(array) > 1:
        m = len(array)//2
        left = array[:m]
        right = array[m:]

        sort(left)
        sort(right)

        i = 0
        j = 0
        k = 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                array[k] = left[i]
                i += 1
            else:
                array[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            array[k] = right[j]
            j += 1
            k += 1
    print('Merging', array)

arr = [1,6,5,2,10,8,7,4,3,9]
sort(arr)

产生预期的正确输出:

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

但是，当我尝试在类中使用此函数时出现错误；我认为与命名空间管理有关。见下文:

class MergeSort(object):

    def __init__(self, array):
        self.array = array

    def sort(self):
        print('Splitting', self.array)
        if len(self.array) > 1:
            m = len(self.array)//2
            left = self.array[:m]
            right = self.array[m:]

            sort(left)
            sort(right)

            i = 0
            j = 0
            k = 0

            while i < len(left) and j < len(right):
                if left[i] < right[j]:
                    self.array[k] = left[i]
                    i += 1
                else:
                    self.array[k] = right[j]
                    j += 1
                k += 1

            while i < len(left):
                self.array[k] = left[i]
                i += 1
                k += 1

            while j < len(right):
                self.array[k] = right[j]
                j += 1
                k += 1
        print('Merging', self.array)

x = MergeSort([1,6,5,2,10,8,7,4,3,9])
x.sort()

产生错误输出:

Splitting [1, 6, 5, 2, 10, 8, 7, 4, 3, 9]
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-15-89509f86277e> in <module>()
      1 x = MergeSort([1,6,5,2,10,8,7,4,3,9])
----> 2 x.sort()

<ipython-input-14-2bba116f00ce> in sort(self)
     11             right = self.array[m:]
     12 
---> 13             sort(left)
     14             sort(right)
     15 

NameError: name 'sort' is not defined

在谷歌搜索之后，我最初的直觉是通过添加前缀 self. 来更改子例程 sort(left) 和 sort(right)，但这会产生位置参数错误。希望就我在这里不理解的内容发表一两条评论。如果我的问题不愚蠢，请投赞成票，如果是的话，请投反对票。

Answer 1

sort(left) 不起作用的原因是，正如您推测的那样，您不能在不指定 self< 的情况下调用 self 上的方法。将其关闭意味着它会查找本地或全局名称 sort，但找不到，并引发 NameError。

self.sort(left) 不起作用的原因是您定义的 API 不能那样工作。您的类将列表作为构造函数参数，然后采用不带参数的 sort，它对构造时传入的列表进行操作。因此，您无法使用不同的数组调用您自己的 sort。如果您尝试 self.sort(left)，您将传递错误数量的参数，就像调用 abs(1, 2) 一样，您会得到相同的 类型错误。

您必须按照您设计的方式使用您的 API:使用新列表创建一个新的 MergeSort 排序器对象，然后对该新对象调用 sort:

leftsorter = MergeSort(left)
leftsorter.sort()
rightsorter = MergeSort(right)
rightsorter.sort()