完美洗牌算法(2)

重要结论：对于2n = 3^k-1长度的数组，恰好只有n个圈，且每个圈头部的起始位置分别是1,3,9,...,3^(k-1).
c代码如下：
数组为{a1,a2,...,a7,b1,b2...b7}

k	m	n2	n2/m	>3
0	1	14	14	y
1	3	14	4	y
2	9	14	0	n

时间复杂度是O(n),空间复杂度是O(1)

#include<stdio.h>
#include<stdlib.h>
#define N 9
#define swap(t,x,y) (t = (x),x = (y),y = (t))
int b[N];
void CycleLeader(int *a,int from,int mod)//一次走环算法
{
    int t,i;
    for (i = from*2 % mod;i != from;i = i*2 % mod)
    {
        t = a[i];
        a[i] = a[from];
        a[from] = t;
    }


}
/*思想：把前n-m个元素(m+1,...,n)和后m个元素(m+1,...n+m)先各自反转，在将整个段反转
void reverse(int *a,int from,int to)//循环位移算法
{
    int t;
    for (;from < to;++from,--to)
    {
        t = a[from];
        a[from] = a[to];
        a[to] = t;
    }
}
void RightRotate(int *a,int num,int n)
{
    reverse(a,1,n-num);
    reverse(a,n-num+1,n);
    reverse(a,1,n);
}
void PerfectShuffle(int *a,int n)
{
    int n2,m,i,k,t;
    if (n >1)
    {
        n2 = n*2;
        //找到 2m = 3^k-1,使得3^k <= 2n < 3^(k+1)
        for (k = 0,m = 1;n2 / m >= 3;++k,m *= 3)
            ;
        m /= 2;
//2m = 3 ^k-1,3 ^k <= 2n < 3^(k+1)
        //把数组中A[m+1,...n+m]那部分循环右移m位

        RightRotate(a+m,m,n);
//对于2m长度的数组，刚好有k个圈，且每个圈的头部为3^i,对每个圈执行CycleLeader算法
        for (i = 0,t = 1;i < k;++i,t *= 3)
        {
            CycleLeader(a,t,m*2+1);
        }
        PerfectShuffle(a+2*m,n-m);
    }
    if (n == 1)
    {
        t = a[1];
        a[1] = a[2];
        a[2] = t;
    }
}
void Shuffle(int *a,int n)
{
    int i,t,n2 = n*2;
    PerfectShuffle(a,n);
    for (i = 2;i <= n2;i += 2)//相邻元素交换算法
    {
        t = a[i-1];
        a[i-1] = a[i];
        a[i] = t;
    }
}

int main()
{
    int a[9] = {0,1,2,3,4,5,6,7,8};
    Shuffle(a,4);
    int i = 0;
    for (i = 1;i <=8;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;
}