本文是看完july博客完美洗牌之后的个人笔记。

题目：把a1,a2,a3,a4,...,an-1 an,b1,b2,b3,...,bn-1,bn变成a1,b1,a2,b1,...,an,bn.要求时间复杂度为O(n),空间复杂度为O(1).

1.位置置换算法：b是新开的一个数组，但是时间复杂度为O(n),空间复杂度为O(n).

void perfectShuttle(int a[],int n){    int n2=n*2,b[N];    for(int i=1;i<=n2;i++)        b[(2*i)%(n2+1)]=a[i];    for(int i=1;i<=n2;i++)        a[i]=b[i];}

2.不管你n是奇数还是偶数,每个位置的元素都将变为第(2*i) % (2n+1)个元素: 

数组下标从1开始，from是圈的头部，mod是要取模的数 mod 应该为 2 * n + 1，时间复杂度O(圈长) 

void CycleLeader(int a[],int from,int mod){    for(int i=from*2%mod;i!=from;i=i*2%mod)        swap(a[i], a[from]);}

3.神级结论: 2*n=(3^k - 1)，则可确定圈的个数及各自头部的起始位置 

 

完美洗牌算法，其算法流程为:

输入数组 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

//翻转字符串时间复杂度O(to - from)void reverse(int *a, int from, int to) {    for (; from < to; ++from, --to)        swap(a[from],a[to]);}//循环右移num位 时间复杂度O(n)void RightRotate(int *a, int num, int n) {    reverse(a, 1, n - num);    reverse(a, n - num + 1, n);    reverse(a, 1, n);}

void PerfectShuffle2(int *a, int n){    int n2, m, i, k, t;    while( n > 1 )    {        // step 1        n2 = n * 2;        for (k = 0, m = 1; n2 / m >= 3; ++k, m *= 3)            ;        m /= 2;        // 2m = 3^k - 1 , 3^k <= 2n < 3^(k + 1)        // step 2        Right_Rotate(a + m, m, n);        // step 3        for (i = 0, t = 1; i < k; ++i, t *= 3) {            CycleLeader(a , t, m * 2 + 1); }        //step 4        a += m * 2; n -= m;    }    // n = 1    swap(a[1],a[2]);}