排序在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]

對於一個遞歸解決方案，請參閱https://stackoverflow.com/a/41293937/1647737