能否使用归并排序对栈进行排序？

Question

栈可以用链表实现。 使用归并排序可以对链表进行排序: 时间复杂度为O(n log n) 空间复杂度为O(n)

使用归并排序对栈进行排序是有意义的。

如果这样，代码会是什么样子呢？

(在快速搜索网络后，我只找到了暴力算法O(n^2))

- Raul

---

你只能使用pop()和push()方法吗？还是你把栈看作一个玻璃盒子，可以随意操纵内部？ - amit

@amit 我认为首先要考虑的是，否则 - 它与数组（一般情况下）有什么区别？ - Alma Do

pop，push，peek，isEmpty 是唯一允许的。 - Raul

这个有用吗：http://www.cs.utep.edu/ofuentes/cs2302/fall11/nonRecursiveMergesort.txt？ - Rahul Tripathi

看起来这是一个数组的实现，我们这里有一个栈。 - Raul

不确定你在这里想要做什么，但是栈定义了一个顺序，后进先出。对其进行排序将使其不再是栈。 - Moshe Gottlieb

Answer 1

可以的。诀窍在于理解堆栈排序后，头是最大元素 - 我们希望从低到高迭代它。但是我们可以在O(n)时间内反转一个堆栈。

reverse(stack):
   s <- new stack
   while stack.isEmpty() == false:
       s.push(stack.pop)
   return s

现在，使用它，并假设您也可以使用size()，实现它相当容易，并且是大多数堆栈实现的标准 - 我们可以实现归并排序：

伪代码：

mergeSort(stack):
   if stack.isEmpty():
       return stack
   s1 <- new stack
   s2 <- new stack
   //   O(n):
   while s1.size() < stack.size():
        s1.push(stack.pop())
   while (stack.isEmpty() == false):
        s2.push(stack.pop())           
   mergeSort(s1) //half the size of stack
   mergeSort(s2) //half the size of stack
   //head of s1 and s2 is the largest element
   s1 <- s1.reverse() //easily implemented in O(n)
   s2 <- s2.reverse()
   //now head of s1 and s2 is the smallest element
   while (s1.isEmpty() == false and s2.isEmpty() == false):
        if (s1.peek() < s2.peek()):
            stack.push(s1.pop())
         else:
            stack.push(s2.pop())
   //the 'tail' of one stack:
   while (s1.isEmpty() == false):
         stack.push(s1.pop())
   while (s2.isEmpty() == false):
         stack.push(s2.pop())
   //head is the largest, stacks are sorted
   return stack

正确性：
基础：停止条件是一个已排序的空栈。
假设：s1和s2已经排序。
步骤：在翻转之后，使用pop()方法移除元素时，s1和s2基本上按从小到大的顺序遍历，在排序区域中。由于我们总是从每个栈中插入较小的元素，并且我们正在从低到高遍历每个栈 - 因此得到的结果堆栈是有序的。

复杂度：
不包括递归调用，每一步都是 O(stack.size()) = O(n)。这与常规归并排序的行为相同，其余的复杂度遵循原始归并排序的相同步骤，以获得O(nlogn)。

- amit

Answer 2

也许我没有理解到重点，但我会这样做：

void mergesortStack(Stack input) {
    if (input.isEmpty()) {
        return;
    }

    Stack stackLeft = new Stack();
    Stack stackRight = new Stack();

    // split
    while (!input.isEmpty()) {
        stackLeft.push(input.pop());
        if (!input.isEmpty()) {
            stackRight.push(input.pop());
        }
    }

    // recurse
    if (!stackLeft.isEmpty() && !stackRight.isEmpty()) {
        mergesortStack(stackLeft);
        mergesortStack(stackRight);
    }

    // merge
    Stack tmpStack = new Stack();
    while (!stackLeft.isEmpty() || !stackRight.isEmpty()) {
        if (stackLeft.isEmpty()) {
            tmpStack.push(stackRight.pop());
        } else if (stackRight.isEmpty()) {
            tmpStack.push(stackLeft.pop());
            // set an appropriate compare method
        } else if (stackLeft.peek().compareTo(stackRight.peek()) >= 0) {
            tmpStack.push(stackLeft.pop());
        } else {
            tmpStack.push(stackRight.pop());
        }
    }

    // reverse stack
    while (!tmpStack.isEmpty()) {
        input.push(tmpStack.pop());
    }
}

- Absurd-Mind

---

你在这里缺少了非常重要的东西。假设递归调用是正确的，每个较小的堆栈都将其头部作为最大值。但你要先推它。这将导致堆栈顺序错误 - 因为头部不再是最大元素。这与算法的正确性相矛盾。它可以很容易地解决 - 但在我看来，这是这个问题中最重要的方面。 - amit

递归阶段中的isEmpty检查似乎是多余的。 - Raul