完美洗牌问题



完美洗牌问题：
（一）有长度为2n的数组{a1,a2...an,b1,b2...bn},希望排序后为{a1,b1,a2,b2...an,bn},希望时间复杂度为O(n),空间复杂度为O(1)

（二）解析：有两副牌，一个人拿的牌为a1,a2,a3...an,另一个人的牌为b1,b2...bn,两个人交叉出牌，则牌的顺序就可以为a1，a2,b1,b2,...an,bn或者b1,a1,b2,a2..bn,an
（a1,b1,a2,b2...）到（b1,a1,b2,a2....)只需要奇数遍历一遍，然后当前元素与后面的元素交换即可。时间复杂度为O(n)

（三）解决：

（1）方法一：
时间复杂度为O(n),空间复杂度为O(n)

根据数组，将前n个数据进入一个队列，后n个数据进入一个队列，然后依次轮流出队列即可。

（2）方法二：
时间复杂度为O(n^2),空间复杂度为O(1);

如：a1,a2,..an,b1,b2..bn
首先定位到b1的位置，然后将b1与a1之间的元素a2...an整体交换，即（a2..an，b1）循环右移一位，即a1,a2..an,b1,b2..bn->a1,b1,a2..an,b2..bn;
然后在将b2，a2之间的元素a3,a4..an与b2交换。。。。。

（3）方法三：分治法
时间复杂度为O(n*lgn),空间复杂度为O(1)

如：当n为偶数时，如a1,a2,a3,a4,b1,b2,b3,b4,
将中间的n个元素循环右移n/2次，得到a1,a2,b1,b2,a3,a4,b3,b4。
然后求解子问题a1,a2,b1,b2和a3,a4,b3,b4即可。

如果n为奇数，如n=5，如a1,a2,a3,a4,a5,b1,b2,b3,b4,b5则先将a5与后面的所有元素循环左移一位，即变成a1,a2,a3,a4,b1,b2,b3,b4,b5,a5,此时的b5,a5已经是我们要的结果了，只需要考虑n=4的情况了。

所以T(n)=2T(n/2)+O(n)

2）代码实现如下：

/*
 a为数组，halflen为数组长度的一半，所以总长度为2*halflen。
 即halflen为每个人手中的牌数目
 数组的下标是从1开始，即数组从a[1,2*halflen]
 */
 void prefect_shuffle2(int *a ,int halflen){
  
  int tempdata;
  if(halflen==1){
   tempdata=a[1];
   a[1]=a[2];
   a[2]=tempdata;
   return ;
  } int totalLen=2*halflen;
  int quarterLen=halflen/2; int i;
 if(halflen%2==1){
  //halflen为奇数
   tempdata=a[halflen];   for(i=halflen+1;i<=totalLen;i++){
     a[i-1]=a[i];
    }
    a[totalLen]=tempdata;
    halflen--;
  } //此时halflen为偶数
 for(i=quarterLen+1;i<=halflen;i++){//将中间的n个数据循环移动
   tempdata=a[i];
   a[i]=a[i+quarterLen];
   a[i+quarterLen]=a[i];
  } perfect_shuffle2(a,quarterLen);
 perfect_shuffle2(a+n,quarterLen);
 }