合併與按升序排列的元件和一個堆棧元件隊列以降序

Question

假設我有與按升序排列的元件，也就是頭<第二<第三< ... <尾

隊列和一個堆元素按降序排列，即top> 2nd> 3rd> ...

它們的大小最多相差1（它們可能大小相同）。

什麼是最有效的方式將它們合併到一個隊列（或棧）作爲一個單獨的排序序列沒有額外的堆棧/隊列？

看來，我認爲迄今爲止最好的是一種基本上是選擇排序的二次算法，它並沒有真正利用隊列和堆棧被預先分類和大小的事實。我想知道我們能做得更好嗎？

Answer 1

就地合併，將結果放在隊列末尾。保持計數，以便知道何時完成。這是O（n）。

這是在Python中。我沒有使用隊列或堆棧類，但你會看到q列表是FIFO，列表是LIFO！

最有趣的調試案例已啓用，所以你可以看到輸出。

def sort(Q, S, debug=False): 
    q = Q 
    s = S 
    size = len(Q) + len(S) 
    handled = 0 
    while handled < size: 
    move_from_queue = len(s) == 0 or (len(q) > 0 and q[0] < s[0]) 
    last_from_stack = (handled == size-1) and (len(s) == 1) 
    if move_from_queue and not last_from_stack: 
     q_front = q[0] 
     q = q[1:] + [q_front] 
     msg = 'moved q[0]=%d to end, q=%r' % (q_front, q) 
    else: 
     (s_top, s) = (s[0], s[1:]) 
     q += [s_top] 
     msg = 'popped s[0]=%d to end of q=%r,s=%r' % (s_top, q, s) 
    handled += 1 
    if debug: 
     print 'Debug-Step %d: %s' % (handled, msg) 
    return (q, s) 

def test_sort(Q, S, debug=False): 
    print 'Pre Q: %r' % Q 
    print 'Pre S: %r' % S 
    (Q, S) = sort(Q, S, debug) 
    print 'Sorted: %r' % Q 
    print 

if __name__ == "__main__": 
    test_sort([1, 3, 7, 9], [2, 5, 5]) 
    test_sort([1, 3, 7], [2, 5, 5]) 
    test_sort([1, 3, 7], [2, 5, 5, 9], True) 
    test_sort([], []) 
    test_sort([1], []) 
    test_sort([], [1]) 

輸出：

 
Pre Q: [1, 3, 7, 9] 
Pre S: [2, 5, 5] 
Sorted: [1, 2, 3, 5, 5, 7, 9] 

Pre Q: [1, 3, 7] 
Pre S: [2, 5, 5] 
Sorted: [1, 2, 3, 5, 5, 7] 

Pre Q: [1, 3, 7] 
Pre S: [2, 5, 5, 9] 
Debug-Step 1: moved q[0]=1 to end, q=[3, 7, 1] 
Debug-Step 2: popped s[0]=2 to end of q=[3, 7, 1, 2],s=[5, 5, 9] 
Debug-Step 3: moved q[0]=3 to end, q=[7, 1, 2, 3] 
Debug-Step 4: popped s[0]=5 to end of q=[7, 1, 2, 3, 5],s=[5, 9] 
Debug-Step 5: popped s[0]=5 to end of q=[7, 1, 2, 3, 5, 5],s=[9] 
Debug-Step 6: moved q[0]=7 to end, q=[1, 2, 3, 5, 5, 7] 
Debug-Step 7: popped s[0]=9 to end of q=[1, 2, 3, 5, 5, 7, 9],s=[] 
Sorted: [1, 2, 3, 5, 5, 7, 9] 

Pre Q: [] 
Pre S: [] 
Sorted: [] 

Pre Q: [1] 
Pre S: [] 
Sorted: [1] 

Pre Q: [] 
Pre S: [1] 
Sorted: [1]