如何在有限制的情況下將一副牌排序？

1樓：鄧毅

分析題目

一副撲克假設有 N 張牌，我們把最上面和最下面串起來變成乙個環，也就是最上面一張牌看作是放在了最下面一張牌下面或者反過來。從而，可能的兩個操作：交換最上面兩張牌簡稱為「交換」，把最上面一張牌移到最下面就是「旋轉」。

如果我們把撲克牌的位置固定，「旋轉」也可以看作是「檢視」和「交換」的視窗在「移動」，以下的描述都採用這樣的方式。

演算法複雜度下限

由於每次「交換」只會讓兩張牌的位置變化 1，我們求出排好序以後各個牌的位置與初始位置差的和，交換次數至少為這個和。可見，最優的演算法最差情況下的複雜度不會低於 O(N^2)。

排序演算法

整個排序過程就是不停的把檢視視窗從頭「移動」到尾，每「移動」一次決定是否「交換」，所以其實進行的就是「氣泡排序（https://

zh.wikipedia.org/wiki/%

E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F

）」。具體的描述如下：

從第 1 張開始，依次「檢視」兩張撲克的順序是否正確，如果不正確則「交換」。然後把視窗往下「移動」。

迴圈的最後會碰到「檢視」第 1 張和第 N 張的情況，此時無論什麼結果（其實必然是反序）均不交換。同時，本輪迴圈結束。

如果本迴圈出現了「交換」操作，轉 1 進行下一輪操作

否則演算法結束

演算法複雜度

最好的情況是撲克牌已經有序，從而第一輪（N 次）迴圈就沒有任何「交換」，從而演算法結束。而對於輸入為反序的時候，第 k 次會讓第 k 大的牌放到自己最終的位置，所以會走完所有的 N 輪才結束，所以是最差的情況，時間複雜度O( N^2 )。

上面描述的演算法，需要乙個額外的計數器，N 不是非常大的時候，可以認為是常數的空間複雜度。

優化當前演算法已經達到了演算法複雜度的下限，所以優化都是小優化，而且有一些和其他假設有關係：

如果排序的人可以記下所有的牌做判斷，可以先掃瞄一次所有的牌不做任何變化，然後選擇乙個更好的起點執行上述演算法。比如，如果牌的順序為 4 5 6 1 2 3，則只需要移動到 1 的位置演算法就結束了。此時，需要 O(N) 的空間進行判斷。

如果演算法進行到了第 N－1 輪，則 3~N 的牌都是有序的，且都大於前兩張，所以只要做一輪比較，如果需要做一次「交換」，則可以停止演算法了，不需要再走完這一輪迴圈。

2樓：

假設牌有n張。

首先，我們找最大的牌。具體來說，比較最頂端的兩張牌，將大的那張放在上面，小的那張丟到最下面去。這時，原來牌堆裡面的第三張牌來到了第二的位置。

此時，重複上面步驟，比較最頂端的兩張牌，將大的那張放在上面，小的那張丟到最下面去。注意到，在這個迴圈中，截止當前為止所知道的最大的牌始終在最上面。因此，經過n-2次迴圈後，整個牌堆中最大的牌就是頭兩張牌中較大的那一張。

找到這最大的一張，放到底部。

接下來我們找第二大的牌。過程和上面類似。只不過，我們只用重複基礎步驟（即比較頂部兩張牌然後把大的放到底部）n-3次。

然後，整個牌堆中第二大的牌就是頭兩張牌中較大的那一張。找到這一張，放到底部。注意，此時從第三張牌來到第二張的是我們在第一次大迴圈中找出的整個牌堆的最大張，把這張放到再放到底部。

此時，底部的那張是最大的牌，倒數第二張是第二大的牌。

接下來進行第三次大迴圈，找第三大的牌。過程類似，不再贅述。

經過n-2次大迴圈後，牌堆最小的兩張牌就在頂部了。把這兩張中較小的放到頂部，較大的放在第二的位置。此時，整個牌堆就是按公升序排列的了。

這個演算法複雜度應該是O(n^2)，不知道能不能做的更好。