完美洗牌算法

题目描述：

有个长度为2n的数组 {a1, a2, a3, ..., an, b1, b2, b3, ..., bn} ，希望排序后 {a1, b1, a2, b2, ...., an, bn} ，请考虑有无时间复杂度 O(n)，空间复杂度 O(1) 的解法。

分析和解法：

解法一：蛮力变换

题目要我们怎么变换，咱们就怎么变换。为了便于分析，我们取 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 已在最后的位置，不需要再交换。如此，经过上述 3 个步骤后，得到我们最后想要的序列。

源代码如下：

#include <iostream>

using namespace std;

void Move(int a[], int n)
{
    if (n < 3 || n % 2 == 1)
        return;
    
    int size = n / 2;  //规模 
    int index, count;
    for (int i = size; i < n - 1; i++)
    {
        count = size - (i - size) - 1;  //交换个数 
        index = i;  //待交换的数的下标 
        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），我们得继续寻找其它方法，看看有无办法能达到题目所预期的 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 在他发表一篇名为：“A Simple In-Place Algorithm for In-Shuffle” 的论文中提出了完美洗牌算法。

什么是完美洗牌问题呢？即给定一个数组

a1，a2，a3， …， an， b1， b2， b3， ...， bn

最终把它置换成

b1， a1， b2， a2， a3， b3，…， bn， an

这个完美洗牌问题本质上与本题完全一致，只要在完美洗牌问题的基础上对它最后的序列 swap 两两相邻元素即可。

2.1、位置置换 perfect_shuffle1 算法

（1）对原始位置的变化做如下分析：

位置变化

（2）依次考察每个位置的变化规律：

从上面的例子我们能看到，前 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) 的位置。

因此，如果题目允许我们再用一个数组的话，我们直接把每个元素放到该放得位置就好了。也就产生了最简单的方法 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) 。我们继续寻找更优的解法。

2.2、完美洗牌算法 perfect_shuffle2

2.2.1、走圈算法 cycle_leader

根据上面变换的节奏，我们可以看出有两个圈

一个是1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1；
一个是3 -> 6 -> 3。

这两个圈可以表示为（1,2,4,8,7,5）和（3,6），且 perfect_shuffle1 算法也已经告诉了我们，不管 n 是奇数还是偶数，每个位置的元素都将变为第（2*i） % （2n+1）个元素：

因此我们只要知道圈里最小位置编号的元素即圈的头部，顺着圈走一遍就可以达到目的，且因为圈与圈是不相交的，所以这样下来，我们刚好走了 O（N）步。

2.2.2、神级结论：若 2 * n =（3^k - 1），则可确定圈的个数及各自头部的起始位置

下面我要引用此论文 “A Simple In-Place Algorithm for In-Shuffle” 的一个结论了，即 对于 2 * n = （3^k-1）这种长度的数组，恰好只有 k 个圈，且每个圈头部的起始位置分别是 1，3，9，...，3^(k-1)。

至此，完美洗牌算法的 “主体工程” 已经完工，只存在一个 “小” 问题：如果数组长度不是（3^k - 1）呢？

若 2 * n != （3^k - 1），则总可以找到最大的整数 m，使得 m < n，并且 2 * m = （3^k - 1）。

对于长度为 2 * m 的数组，整理元素后剩余的 2 *（n - m）长度，递归调用完美洗牌算法即可。

2.2.3、完美洗牌算法 perfect_shuffle3

从上文的分析过程中也就得出了我们的完美洗牌算法，其算法流程为：

输入数组　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]那部分循环移 m 位
step 3 对每个 i = 0,1,2..k - 1，3^i 是个圈的头部，做 cycle_leader 算法，数组长度为 m，所以对 2 * m + 1 取模。
step 4 对数组的后面部分 a[2 * m + 1.. 2 * n] 继续使用本算法, 这相当于 n 减小了 m 。

2.2.4、perfect_shuffle2 算法解决其变形问题

原始问题要输出 a1, b1, a2, b2……an, bn，而完美洗牌却输出的是b1, a1, b2, a2,……bn, an。解决办法非常简单：交换两两相邻元素即可（当然，你也可以让原数组第一个和最后一个不变，中间的 2 * (n - 1) 项用原始的标准完美洗牌算法做），只是在完美洗牌问题时间复杂度 O(N) 空间复杂度 O(1) 的基础上再增加 O(N) 的时间复杂度，故总的时间复杂度 O(N) 不变，且理所当然的保持了空间复杂度 O(1) 。至此，咱们的问题得到了圆满解决！

源代码如下：

#include <iostream>
using namespace std;

class Solution
{
    public:
        // 完美洗牌算法
        void PerfectShuffle(int *a, int n)
        {
            while(n >= 1)
            {
                // 计算环的个数
                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;
                // 循环左移n-m位
                LeftRotate(a + m, n - m, n);
                // k个环 环起始位置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:
        // 翻转 start 开始位置 end 结束位置
        void Reverse(int *a, int start, int end)
        {
            while(start < end)
            {
                swap(a[start], a[end]);
                ++start;
                --end;
            }//while
        }
        // 循环右移m位 n数组长度 下标从1开始
        void LeftRotate(int *a, int m, int n)
        {
            // 翻转前m位
            Reverse(a, 1, m);
            // 翻转剩余元素
            Reverse(a, m + 1, 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;
            // 按环移动位置
            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）。

特别注意：

本次题目比较简单，但是要求限制有点苛刻。完美洗牌算法和神级结论还需细致的了解。

参考资料：《编程之法》The Art of Programming By July
[经典面试题]完美洗牌算法