[经典面试题]完美洗牌算法

题目

有个长度为2n的数组{a1,a2,a3,…,an,b1,b2,b3,…,bn}，希望排序后{a1,b1,a2,b2,….,an,bn}，请考虑有无时间复杂度o(n)，空间复杂度0(1)的解法。

来源

2013年UC的校招笔试题

思路一

第①步、确定b1的位置，即让b1跟它前面的a2，a3，a4交换：

a1，b1，a2，a3，a4，b2，b3，b4

第②步、接着确定b2的位置，即让b2跟它前面的a3，，a4交换：

a1，b1，a2，b2，a3，a4，b3，b4

第③步、b3跟它前面的a4交换位置：

a1，b1，a2，b2，a3，b3，a4，b4

b4已在最后的位置，不需要再交换。如此，经过上述3个步骤后，得到我们最后想要的序列。但此方法的时间复杂度为O（n^2）

代码一

/*———————————————* 日期：2015-02-13* 作者：SJF0115* 题目: 完美洗牌算法* 来源：2013年UC的校招笔试题* 博客：———————————————–*/#include <iostream>using namespace std;:void PerfectShuffle(int *A,int n){if(n <= 1){return;}size = 2*n;int index,count;for(int i = n;i < size;++i){// 交换个数count = n – (i – n) – 1;// 待交换index = i;for(int j = 1;j <= count;++j){swap(A[index],A[i-j]);index = i – j;}//for}//for}};int main() {Solution solution;int A[] = {1,2,3,4,5,6,7,8};solution.PerfectShuffle(A,4);for(int i = 0;i < 8;++i){cout<<A[i]<<” “;}//forcout<<endl;}

思路二

我们每次让序列中最中间的元素进行两两交换。还是上面的例子：

a1，a2，a3，a4，b1，b2，b3，b4

第①步：交换最中间的两个元素a4，b1：

a1，a2，a3，b1，a4，b2，b3，b4

第②步：最中间的两对元素各自交换：

a1，a2，b1，a3，b2，a4，b3，b4

第③步：交换最中间的三对元素：

a1，b1，a2，b2，a3，b3，a4，b4

此思路同上述思路一样，时间复杂度依然为O（n^2）。仍然但不到题目要求。

代码二

/*———————————————* 日期：2015-02-13* 作者：SJF0115* 题目: 完美洗牌算法* 来源：2013年UC的校招笔试题* 博客：———————————————–*/;class Solution {public:void PerfectShuffle(int *A,int n){if(n <= 1){return;}left = n – 1,right = n;// 交换次数for(int i = 0;i < n-1;++i){for(int j = left;j < right;j+=2){swap(A[j],A[j+1]);}//for–left;++right;}//for}};int main() {Solution solution;int A[] = {1,2,3,4,5,6,7,8,9,10};solution.PerfectShuffle(A,5);for(int i = 0;i < 10;++i){cout<<A[i]<<” “;}//forcout<<endl;}

思路三（完美洗牌算法）

玩过扑克牌的朋友都知道，在一局完了之后洗牌，洗牌人会习惯性的把整副牌大致分为两半，两手各拿一半对着对着交叉洗牌。

2004年，microsoft的Peiyush Jain在他发表一篇名为：“A Simple In-Place Algorithm for In-Shuffle”的论文中提出了完美洗牌算法。

什么是完美洗牌问题呢？即给定一个数组a1,a2,a3,…an,b1,b2,b3..bn,最终把它置换成b1,a1,b2,a2,…bn,an。这个完美洗牌问题本质上与本题完全一致，只要在完美洗牌问题的基础上对它最后的序列swap两两相邻元素即可。

（1）对原始位置的变化做如下分析：

（2）依次考察每个位置的变化规律： a1：1 -> 2 a2：2 -> 4 a3：3 -> 6 a4：4 -> 8 b1：5 -> 1 b2：6 -> 3 b3：7 -> 5 b4：8 -> 7

对于原数组位置i的元素，新位置是(2*i)%(2n+1)，注意，这里用2n表示原数组的长度。后面依然使用该表述方式。有了该表达式，困难的不是寻找元素在新数组中的位置，而是为该元素“腾位置”。如果使用暂存的办法，空间复杂度必然要达到O(N)，因此，需要换个思路。

（3）我们这么思考：a1从位置1移动到位置2，那么，位置2上的元素a2变化到了哪里呢？继续这个线索，我们得到一个“封闭”的环：

1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1

沿着这个环，可以把a1、a2、a4、b4、b3、b1这6个元素依次移动到最终位置；显然，因为每次只移动一个元素，代码实现时，只使用1个临时空间即可完成。(即：a=t;t=b;b=a) 此外，该变化的另外一个环是：

3 -> 6 -> 3

沿着这个环，可以把a3、b2这2个元素依次移动到最终位置。

// 走圈算法void CycleLeader(int *a,int start, int n) {int pre = a[start];= 2 * n + 1;// 实际位置int next = start * 2 % mod;// 按环移动位置while(next != start){swap(pre,a[next]);next = 2 * next % mod;}//whilea[start] = pre;}看着它或是汹涌或是平静，然而一直相随，不离不弃。