堆栈的归并排序

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

我假设您这样做是为了学习合并排序或后进先出法，但如果不是，因为您的 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 数组添加到堆栈之前，您需要确保添加的数字大于堆栈的当前头部（Last in）。如果不大于，则需要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]

堆栈的归并排序

Merge-sort for Stacks

python

sorting

merge

stack

mergesort