在 2n 空间中对堆栈进行排序

Question

我已经在Java和C中找到了这个问题的几个实现，但我还没有找到一个使用JavaScript的示例。这是一个相当常见的技术面试问题：

在2n空间中对堆栈进行排序。（仅使用2个堆栈对堆栈进行排序）

Answer 1

我们可以在给定堆栈和临时缓冲区的情况下实现简单的非递归气泡排序：

1. 迭代地从堆栈中弹出两个元素，如果第一个元素更大，则交换这两个元素，然后将它们推回缓冲区。
2. 重复步骤 1，但反转方向，因此缓冲区中的所有元素最终将返回到堆栈上。

重复步骤1.和2.直到不再需要交换元素。

function bubble(stack, buffer, up = true) {
  let swaps = 0;
  let last = stack.pop();
  while (stack.length > 0) {
    let next = stack.pop();
    if (up ? last > next : last < next) swaps++;
    else [next, last] = [last, next];
    buffer.push(next);
  }
  buffer.push(last);
  return swaps;
}

function sort(stack, up = true, buffer = []) {
  do bubble(stack, buffer, !up);
  while (bubble(buffer, stack, up) > 0);
  return stack;
}

// Example:
console.log(sort([6,3,9,3,2,8])); // [2, 3, 3, 6, 8, 9]