完美洗牌问题，给定一个数组a1,a2,a3,...an,b1,b2,b3..bn,把它最终设置为b1,a1,b2,a2,...bn,an这样的。
O(n)的算法，O(n)的空间。
对于前n个数，映射为f(i)=2 * i + 1, 0 <= i < n / 2; 比如0->1, 1->3
对于后n个数，映射为f(i)=2(i - n/2), n / 2 <= i < n; 比如n/2->0, n/2 + 1->2... 并且f(i) =2(i - n/2)=2*i-n=2*i+1-(n+1)=(2*i+1)%(n+1)。
统一起来，映射为f(i) = (2 * i + 1) % (n + 1).
void perfectShuffle1(int arr[], int n) {
int* tmp = new int[n];
for (int i = ; i < n; ++i) {
tmp[((i << ) + ) % (n + )] = arr[i];
}
for (int i = ; i < n; ++i) {
arr[i] = tmp[i];
}
delete[] tmp;
}
分治法，O(nlgn)的算法，O(lgn)的空间。
Line 4-11 主要就是处理好数组的一半为奇数的情部分。
当n/4!=0的时候，数组的一半为奇数。此时要将[n/2,n)的数往左移，把第n/2-1个数（前一半的最后一个数）放到末尾，这样，最后两个数就排好了。问题就转化成了数组的一半是偶数的情况。
当数组的一半是偶数时，只需要把前一半的后半部分和后一半的前半部分交换一下，就达到分治的目的了。
void perfectShuffle2(int arr[], int n) {
if (n % != ) return;
if (n <= ) return;
if (n % != ) {
int tmp = arr[n / - ];
for (int i = n / ; i < n; ++i) {
arr[i - ] = arr[i];
}
arr[n - ] = tmp;
n -= ;
}
for (int i = ; i < n / ; ++i) {
swap(arr[n / + i], arr[n / + i]);
}
perfectShuffle2(arr, n / );
perfectShuffle2(arr + n / , n / );
}
主要参考自：http://blog.csdn.net/caopengcs/article/details/10176093， 里面提到的第三种解法没去看，感觉面试不会考就先不费力去理解了。
洗牌的问题就比较简单，其实相当于从数组中随机选出m个数，见之前的博文。只不过这里m=n而已。
void shuffle(int arr[], int n) {
srand(time(NULL));
for (int i = ; i < n; ++i) {
swap(arr[i], arr[i + rand() % (n - i)]);
}
}
这个和网上提到的FisherYates洗牌算法的原理是一样的。
