python - 堆栈的归并排序

Question

知道为什么我的堆栈合并排序不起作用吗？它与我的数组合并排序非常相似，但它确实有效。我的递归设置错误吗？

谢谢!

def sort(stack):
    if len(stack) > 1:
        middle = len(stack) // 2
        stack_len = len(stack)
        left = Stack()
        right = Stack()
        for i in range(middle):
            left.push(stack.pop())
        for i in range(middle, stack_len):
            right.push(stack.pop())
        sort(left)
        sort(right)
        while(not left.is_empty() and not right.is_empty()):
            if (left.top() < right.top()):
                stack.push(right.pop())
            else:
                stack.push(left.pop())
        while(not left.is_empty()):
            stack.push(left.pop())
        while(not right.is_empty()):
            stack.push(right.pop())

这是我的 Stack ADT 实现:

class Stack:

    def __init__(self):
        self._data = []

    def __len__(self):
        return len(self._data)

    def is_empty(self):
        return len(self) == 0

    def push(self, i):
        self._data.append(i)

    def pop(self):
        if not self.is_empty():
           return self._data.pop()
        raise IndexError('Cannot pop an empty Stack.')

    def top(self):
        if not self.is_empty():
            return self._data[len(self) - 1]
        raise IndexError('Cannot check the top of an empty Stack.')

我的测试用例是:

if __name__ == '__main__':
    s = Stack()
    s.push(8)
    s.push(0)
    s.push(-4)
    s.push(11)
    s.push(19)
    s.push(21)
    s.push(3)
    s.push(14)
    s.push(1)
    s.push(14)
    print(s._data)
    sort(s)
    print(s._data)

给出:

[8, 0, -4, 11, 19, 21, 3, 14, 1, 14]

[19, 14, 1, 21, 3, 14, -4, 8, 0, 11]

Answer 1

我假设您这样做是为了学习合并排序或 LIFO，但如果不是，因为您的 stack只是一个Python列表(数组)，函数 sorted(s._data)或s._data.sort()两者都能满足您的需求。如果您需要继续堆栈，那么...

首先，调试:

如果你想了解你的错误，你可以放置一些 print()语句来查看代码每个阶段的堆栈情况。您的排序功能很好，并且可以正确分隔数组。该缺陷存在于合并部分。算法的合并部分发生在递归调用sort()之后。在有 3 个 while 循环的部分中。根据您的示例输入，最终这些数组将被合并:

MERGING
L [19]
R [11, -4]

由于您使用堆栈 LIFO 执行此操作，因此使用 pop()基于此条件:left.top() < right.top() ，生成的新堆栈数组变为: [19, -4, 11] 。 Last in, First, out，意味着一旦 Left 数组为空，则第二个添加 -4，因为 Right 已被清空。但是，通过正确的合并，该数组将被合并排序，并且应该像这样合并:

[-4, 11, 19]

您的下一次合并是这样的:

MERGING
L [8, 0]
R [19, -4, 11]

新堆栈的结果是:[11, 0, 8, -4, 19] ，这最终导致 19 首先添加到最终堆栈中，因此 19 位于结果中索引 0 的位置，您将得到: [19, 14, 1, 21, 3, 14, -4, 8, 0, 11]

分辨率:

要解决此问题，您应该使用 queue相反，这将是 FIFO，并且您总是首先将最低的数字添加到队列中，该数字将位于数组的索引 0 处(即从左到右移动)。如果您绝对必须使用 stack并继续 append和.pop()那么，我建议:

首先，在合并部分，合并优先级较高的较小数字。然后，在合并部分将 Left 或 Right 数组添加到堆栈之前，需要确保要添加的数字大于堆栈的当前头(最后一个)。如果它不更大，那么您需要 pop()将堆栈放入新数组或左/右数组(无论您不处理哪个数组)，直到下一个添加的值实际上大于堆栈的头部。然后，继续使用相同的方法，仅将大于堆栈头部的值添加到堆栈中，记住也要按正确的顺序将弹出的值添加回堆栈。

代码更新解决方案

以下是作为维护堆栈方法的解决方案添加的代码:

while(not left.is_empty() and not right.is_empty()):
    if (left.top() > right.top()):
        if stack.is_empty() or stack.top() <= right.top():
            stack.push(right.pop())
        else:
            left.push(stack.pop())
    else:
        if stack.is_empty() or stack.top() <= left.top():
            stack.push(left.pop())
        else:
            right.push(stack.pop())
while(not left.is_empty()):
    if stack.is_empty() or stack.top() <= left.top():
        stack.push(left.pop())
    else:
        right.push(stack.pop())
while(not right.is_empty()):
    if stack.is_empty() or stack.top() <= right.top():
        stack.push(right.pop())
    else:
        left.push(stack.pop())
while(not left.is_empty()):
    stack.push(left.pop())

更新解决方案:[-4, 0, 1, 3, 8, 11, 14, 14, 19, 21]