被大腾讯问到了完美洗牌算法，瞬间就跪了，其实原来看过，只可惜都忘了啊，现在在补充进来吧。
其实完美洗牌算法，应该给我说明白题，最少举个例子吧，当时确实大意了，也没问清楚就直接不会了，其实题意是有个长度为2n的数组{a1,a2,a3,a4,..,an,b1,b2,b3,b4,...,bn},希望排序后{a1,b1,a2,b2,...,an,bn},最好要求时间复杂度为O(n),空间复杂度为O(1)。
解法一：蛮力交换方法
1.1 说白了就是b1和a2,a3,a4,...,an交换，然后是b2和a3,a4,a5,...，an交换，直到bn不交换。复杂度O(n2),肯定不行。
1.2中间交换
交换中间的元素方法，例如：
a1,a2,a3,a4,b1,b2,b3,b4交换a4,b1为：a1,a2,a3,b1,a4,b2,b3,b4
交换中间两个，交换a3,b1和a4,b2为a1,a2,b1,a3,b2,a4,b3,b4,
下一次交换中间三个，依次增加，最后即可但时间复杂度依然为O(n2)
解法二：完美洗牌算法O(n)
有人研究出了完美洗牌算法可以将a1,a2,a3,a4,b1,b2,b3,b4通过O(n)变成b1,a1,b2,a2,b3,a4,b4,a4，通过两两交换即可完成a1,b1,a2,b2,a3,b3,a4,b4.这里来说一下如何用O(n)完成。
2.1 位置置换算法，需要空间复杂度O(n),时间复杂度O(n)
原序：a1,a2,a3,a4,b1,b2,b3,b4
位置：1, 2 , 3, 4 , 5 , 6 , 7 , 8
修改：b1,a1,b2,a2,b3,a3,b4,a4
可以看出1->2;2->4,3->6,4->8,5->1,6->3,7->5,8->7上即第i个元素放到了第(2*i)%(2*n+1)位置上
代码：
1 void pefect_shuffle1(int *a,int n){ 2 int n2=n*2,i,b[N]; 3 for(int i=1;i<=n2;i++) 4 { 5 b[(i*2)%(n2+1)]=a[i]; 6 } 7 for(int i=1;i<=n2;i++) 8 a[i]=b[i]; 9 }
我们注意到：1->2->4->8->7->5->1;和3->6->3这就是完美洗牌的关键后面继续说。
2.2 分治处理O(nlogn)
可以将大问题化成两个子问题处理，例如：
n=4情况
a1,a2,a3,a4,b1,b2,b3,b4，交换前半段的后n/2和后半段的前n/2为a1,a2,b1,b2,a3,a4,b3,b4就变成两个子问题。
n=5情况
a1,a2,a3,a4,a5,b1,b2,b3,b4,b5，将中间的给放到最后，剩下的前移即：a1,a2,a3,a4,b1,b2,b3,b4,b5,a5，变成处理n=4情况
1 #include <iostream> 2 using namespace std; 3 void perfect_shuffle2(int *a ,int n) 4 { 5 int t,i; 6 if(n==1) 7 { 8 swap(a[1],a[2]); 9 return; 10 } 11 int n2=n*2,n3=n/2; 12 if(n%2==1) 13 { 14 t=a[n]; 15 for(i=n+1;i<=n2;i++) 16 { 17 a[i-1]=a[i]; 18 } 19 a[n2]=t; 20 --n; 21 } 22 for(i=n3+1;i<=n;i++) 23 { 24 t=a[i]; 25 a[i]=a[i+n3]; 26 a[i+n3]=t; 27 } 28 perfect_shuffle2(a,n3); 29 perfect_shuffle2(a+n,n3); 30 }
时间复杂度O(nlogn),空间不算递归调用栈的话为O(1)
2.3 真正完美算法O(n),O(1)
利用走圈方法：
1->2->4->8->7->5->1;
3->6->3;
1 void circle_leader(int *a ,int form ,int mod) //mod=2*n+1 2 { 3 int last=a[from],t,i; 4 for(i=from*2%mod;i!=from;i=i*2%mod) 5 { 6 t=a[i]; 7 a[i]=last; 8 last=t; 9 } 10 a[from]=last; 11 }
神级结论：若2*n=(3^k-1)，则可以确定圈的个数及各自头部的起始位置
对于2*n=(3^k-1)这种长度的数组，恰好只有k个圈，且每个圈头部的起始位置分别为：1,3,9，...，3^(k-1)。
原文：http://www.cnblogs.com/zmlctt/p/4001088.html