完美洗牌算法

題目描述：

有個長度為2n的數(shù)組 {a1, a2, a3, ..., an, b1, b2, b3, ..., bn} 调缨，希望排序后 {a1, b1, a2, b2, ...., an, bn} 词顾，請考慮有無時間復雜度 O(n)，空間復雜度 O(1) 的解法贷盲。

分析和解法：

解法一：蠻力變換

題目要我們怎么變換，咱們就怎么變換。為了便于分析，我們?nèi)?n = 4丁眼，那么題目要求我們把

a1，a2昭殉，a3苞七，a4， b1挪丢，b2蹂风，b3，b4

變成

a1乾蓬，b1惠啄，a2，b2，a3礁阁，b3，a4族奢，b4

1.1姥闭、步步前移

仔細觀察變換前后兩個序列的特點，我們可做如下一系列操作：

第①步越走、確定 b1 的位置棚品，即讓 b1 跟它前面的 a2，a3廊敌，a4 交換：

a1铜跑，b1，a2骡澈，a3锅纺，a4， b2肋殴，b3囤锉，b4

第②步、接著確定 b2 的位置护锤，即讓 b2 跟它前面的 a3官地，a4 交換：

a1，b1烙懦，a2驱入，b2，a3氯析，a4亏较， b3，b4

第③步魄鸦、b3 跟它前面的 a4 交換位置：

a1宴杀，b1，a2拾因，b2旺罢，a3，b3绢记，a4扁达，b4

b4 已在最后的位置，不需要再交換蠢熄。如此跪解，經(jīng)過上述 3 個步驟后，得到我們最后想要的序列签孔。

源代碼如下：

#include <iostream>

using namespace std;

void Move(int a[], int n)
{
    if (n < 3 || n % 2 == 1)
        return;
    
    int size = n / 2;  //規(guī)模 
    int index, count;
    for (int i = size; i < n - 1; i++)
    {
        count = size - (i - size) - 1;  //交換個數(shù) 
        index = i;  //待交換的數(shù)的下標 
        for (int j = 1; j <= count; j++)
        {
            swap(a[index], a[i - j]);
            index = i - j;
        }
    }
}

int main()
{
    int a[100];
    int n = 0;
    while(cin.peek() != '\n')  cin >> a[n++];
    Move(a, n);
    for (int i = 0; i < n; i++)
        cout << a[i] << " " ;
    cout << endl;
    return 0;
}

分析：但此方法的時間復雜度為 O（N^2）叉讥，我們得繼續(xù)尋找其它方法窘行，看看有無辦法能達到題目所預期的 O（N）的時間復雜度。

1.2图仓、中間交換

當然罐盔，除了如上面所述的讓 b1，b2救崔，b3惶看，b4 步步前移跟它們各自前面的元素進行交換外，我們還可以每次讓序列中最中間的元素進行交換達到目的六孵。還是用上面的例子纬黎，針對 a1，a2劫窒，a3本今，a4，b1主巍，b2诈泼，b3，b4

第①步：交換最中間的兩個元素 a4煤禽，b1铐达，序列變成：

a1，a2檬果，a3 瓮孙，b1，a4选脊， b2杭抠，b3，b4

第②步恳啥，讓最中間的兩對元素各自交換：

a1偏灿，a2 ，b1钝的，a3翁垂，b2，a4硝桩， b3沿猜，b4

第③步，交換最中間的三對元素碗脊，序列變成：

a1啼肩，b1，a2，b2祈坠，a3害碾，b3，a4赦拘，b4

同樣蛮原，此法同解法 1.1、步步前移一樣另绩，時間復雜度依然為 O（N^2）。

源代碼如下：

#include <iostream>

using namespace std;

void Move(int a[], int n)
{
    if (n < 3 || n % 2 == 1)
        return;
        
    int size = n / 2;
    int count = 1;
    for (int i = size; i > 1; i--)
    {
        for (int j = size - count; j < size + count; j += 2)
        {
            swap(a[j], a[j + 1]);   
        }   
        count++;
    }   
} 

int main()
{
    int a[100];
    int n = 0;
    while(cin.peek() != '\n')  cin >> a[n++];
    Move(a, n);
    for (int i = 0; i < n; i++)
        cout << a[i] << " " ;
    cout << endl;
    return 0;
}

分析：此思路同上述思路一樣花嘶，時間復雜度依然為 O（n^2）笋籽，仍然達不到題目要求。

解法二：完美洗牌算法

玩過撲克牌的朋友都知道椭员，在一局完了之后洗牌车海，洗牌人會習慣性的把整副牌大致分為兩半，兩手各拿一半對著對著交叉洗牌隘击。

2004年侍芝，microsoft 的 Peiyush Jain 在他發(fā)表一篇名為：“A Simple In-Place Algorithm for In-Shuffle” 的論文中提出了完美洗牌算法。

什么是完美洗牌問題呢埋同？即給定一個數(shù)組

a1州叠，a2，a3凶赁， …咧栗， an， b1虱肄， b2致板， b3， ...咏窿， bn

最終把它置換成

b1斟或， a1， b2集嵌， a2萝挤， a3， b3根欧，…平斩， bn， an

這個完美洗牌問題本質(zhì)上與本題完全一致咽块，只要在完美洗牌問題的基礎(chǔ)上對它最后的序列 swap 兩兩相鄰元素即可绘面。

2.1、位置置換 perfect_shuffle1 算法

（1）對原始位置的變化做如下分析：

位置變化

（2）依次考察每個位置的變化規(guī)律：

從上面的例子我們能看到，前 n 個元素中揭璃，

第 1 個元素 a1 到了原第 2 個元素 a2 的位置晚凿，即 1 -> 2；
第 2 個元素 a2 到了原第 4 個元素 a4 的位置瘦馍，即 2 -> 4歼秽；
第 3 個元素 a3 到了原第 6 個元素 b2 的位置，即 3 -> 6情组；
第 4 個元素 a4 到了原第 8 個元素 b4 的位置燥筷，即 4 -> 8；

那么推廣到一般情況即是：前 n 個元素中院崇，第 i 個元素去了 第（2 * i）的位置肆氓。

上面是針對前 n 個元素，那么針對后 n 個元素底瓣，可以看出：

第 5 個元素 b1 到了原第 1 個元素 a1 的位置谢揪，即 5 -> 1；
第 6 個元素 b2 到了原第 3 個元素 a3 的位置捐凭，即 6 -> 3拨扶；
第 7 個元素 b3 到了原第 5 個元素 b1 的位置，即 7 -> 5茁肠；
第 8 個元素 b4 到了原第 7 個元素 b3 的位置患民，即 8 -> 7；

推廣到一般情況是：后 n 個元素垦梆，第 i 個元素去了第 (2 * (i - n) ) - 1 = 2 * i - (2 * n + 1) = (2 * i) % (2 * n + 1) 的位置酒奶。

當 0 < i < n 時， 原式 = (2 * i) % (2 * n + 1) = 2 * i奶赔；
當 i > n 時惋嚎，原式 (2 * i) % (2 * n + 1) 保持不變。

再綜合到任意情況：任意的第 i 個元素站刑，我們最終換到了 (2 * i) % (2 * n + 1) 的位置另伍。

因此，如果題目允許我們再用一個數(shù)組的話绞旅，我們直接把每個元素放到該放得位置就好了摆尝。也就產(chǎn)生了最簡單的方法 perfect_shuffle1 。

源代碼如下：

#include <iostream>

using namespace std;

void PerfectShuffle1(int a[], int n)
{
    if (n < 3 || n % 2 == 1)
        return;
        
    int b[n];
    for (int i = 1; i < n - 1; i++)
        b[(i * 2) % (n - 1)] = a[i];
    for (int j = 1; j < n - 1; j++)
        a[j] = b[j];
}

int main()
{
    int a[100];
    int n = 0;
    while(cin.peek() != '\n')  cin >> a[n++];
    PerfectShuffle1(a, n);
    for (int i = 0; i < n; i++)
        cout << a[i] << " " ;
    cout << endl;
    return 0;
}

分析：它的時間復雜度雖然是 O(n)因悲，但其空間復雜度卻是 O(n)堕汞，仍不符合本題所期待的時間 O(n)，空間 O(1) 晃琳。我們繼續(xù)尋找更優(yōu)的解法讯检。

2.2琐鲁、完美洗牌算法 perfect_shuffle2

2.2.1、走圈算法 cycle_leader

根據(jù)上面變換的節(jié)奏人灼，我們可以看出有兩個圈

一個是1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1围段；
一個是3 -> 6 -> 3。

這兩個圈可以表示為（1,2,4,8,7,5）和（3,6）投放，且 perfect_shuffle1 算法也已經(jīng)告訴了我們奈泪，不管 n 是奇數(shù)還是偶數(shù)，每個位置的元素都將變?yōu)榈冢?*i） % （2n+1）個元素：

因此我們只要知道圈里最小位置編號的元素即圈的頭部灸芳，順著圈走一遍就可以達到目的涝桅，且因為圈與圈是不相交的，所以這樣下來烙样，我們剛好走了 O（N）步冯遂。

2.2.2、神級結(jié)論：若 2 * n =（3^k - 1）误阻，則可確定圈的個數(shù)及各自頭部的起始位置

下面我要引用此論文 “A Simple In-Place Algorithm for In-Shuffle” 的一個結(jié)論了，即 對于 2 * n = （3^k-1）這種長度的數(shù)組晴埂，恰好只有 k 個圈究反，且每個圈頭部的起始位置分別是 1，3儒洛，9精耐，...，3^(k-1)琅锻。

至此卦停，完美洗牌算法的 “主體工程” 已經(jīng)完工，只存在一個 “小” 問題：如果數(shù)組長度不是（3^k - 1）呢恼蓬？

若 2 * n != （3^k - 1）惊完，則總可以找到最大的整數(shù) m，使得 m < n处硬，并且 2 * m = （3^k - 1）小槐。

對于長度為 2 * m 的數(shù)組，整理元素后剩余的 2 *（n - m）長度荷辕，遞歸調(diào)用完美洗牌算法即可凿跳。

2.2.3、完美洗牌算法 perfect_shuffle3

從上文的分析過程中也就得出了我們的完美洗牌算法疮方，其算法流程為：

輸入數(shù)組　a[1..2 * n]
step 1 找到 2 * m = 3^k - 1 使得 3^k <= 2 * n < 3^(k +1)
step 2 把 a[m + 1..n + m]那部分循環(huán)移 m 位
step 3 對每個 i = 0,1,2..k - 1控嗜，3^i 是個圈的頭部，做 cycle_leader 算法骡显，數(shù)組長度為 m疆栏，所以對 2 * m + 1 取模曾掂。
step 4 對數(shù)組的后面部分 a[2 * m + 1.. 2 * n] 繼續(xù)使用本算法, 這相當于 n 減小了 m 。

2.2.4承边、perfect_shuffle2 算法解決其變形問題

原始問題要輸出 a1, b1, a2, b2……an, bn遭殉，而完美洗牌卻輸出的是b1, a1, b2, a2,……bn, an。解決辦法非常簡單：交換兩兩相鄰元素即可（當然博助，你也可以讓原數(shù)組第一個和最后一個不變险污，中間的 2 * (n - 1) 項用原始的標準完美洗牌算法做），只是在完美洗牌問題時間復雜度 O(N) 空間復雜度 O(1) 的基礎(chǔ)上再增加 O(N) 的時間復雜度富岳，故總的時間復雜度 O(N) 不變蛔糯，且理所當然的保持了空間復雜度 O(1) 。至此窖式，咱們的問題得到了圓滿解決蚁飒！

源代碼如下：

#include <iostream>
using namespace std;

class Solution
{
    public:
        // 完美洗牌算法
        void PerfectShuffle(int *a, int n)
        {
            while(n >= 1)
            {
                // 計算環(huán)的個數(shù)
                int k = 0;
                // 3^1
                int r = 3;
                // 2 * m  = 3^k - 1
                // m <= n  ->  2 * m <= 2 * n  -> 3^k - 1 <= 2 * n
                // 尋找最大的k使得3^k - 1 <= 2*n
                while(r - 1 <= 2 * n)
                {
                    r *= 3;
                    ++k;
                }//while
                int m = (r / 3 - 1) / 2;
                // 循環(huán)左移n-m位
                LeftRotate(a + m, n - m, n);
                // k個環(huán) 環(huán)起始位置start: 1,3...3^(k-1)
                for(int i = 0, start = 1; i < k; ++i, start *= 3)
                {
                    // 走圈
                    CycleLeader(a, start, m);
                }//for
                a += 2 * m;
                n -= m;
            }
        }
    private:
        // 翻轉(zhuǎn) start 開始位置 end 結(jié)束位置
        void Reverse(int *a, int start, int end)
        {
            while(start < end)
            {
                swap(a[start], a[end]);
                ++start;
                --end;
            }//while
        }
        // 循環(huán)右移m位 n數(shù)組長度 下標從1開始
        void LeftRotate(int *a, int m, int n)
        {
            // 翻轉(zhuǎn)前m位
            Reverse(a, 1, m);
            // 翻轉(zhuǎn)剩余元素
            Reverse(a, m + 1, n);
            // 整體翻轉(zhuǎn)
            Reverse(a, 1, n);
        }
        // 走圈算法
        void CycleLeader(int *a, int start, int n)
        {
            int pre = a[start];
            // 2 * i % (2 * n + 1)
            int mod = 2 * n + 1;
            // 實際位置
            int next = start * 2 % mod;
            // 按環(huán)移動位置
            while(next != start)
            {
                swap(pre,a[next]);
                next = 2 * next % mod;
            }//while
            a[start] = pre;
        }
};


int main()
{
    Solution solution;
    int a[100];
    int n = 0;
    while(cin.peek() != '\n')  cin >> a[++n];
    solution.PerfectShuffle(a, n/2);
    for (int i = 1; i <= n; i += 2)
        swap(a[i], a[i + 1]);
    for (int i = 1; i <= n; i++)
    {
        cout << a[i] << " " ;
    }//for
    cout << endl;
    return 0;
}

分析：時間復雜度為 O（n），空間復雜度為 O（1）萝喘。

特別注意：

本次題目比較簡單淮逻，但是要求限制有點苛刻。完美洗牌算法和神級結(jié)論還需細致的了解阁簸。

參考資料：《編程之法》The Art of Programming By July
[經(jīng)典面試題]完美洗牌算法