完美洗牌算法
题目描述：
有个长度为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
[经典面试题]完美洗牌算法
