手摇算法及其应用

        手摇算法也叫三次反转算法，我们可以通过一个简单例子引入该算法。若要将一个字符串abcdef变成defabc，简单的方法是用一个辅助数组来做，但是这种方式有O(n)的空间开销，因此在实际面试中，这种方法是不合格的。这时我们可以通过手摇算法轻松加愉快的解决这个问题，即首先反转abc将其变成cba（这可以通过设定两个指针指向首尾元素，然后通过交换指针指向的元素并将两指针往中间移动的方式来实现），同理def变成fed。此时字符串变为cbafed。再对其进行一次反转则达到了我们的要求defabc。是不是很简单！你在逗我吗 ？但是简单归简单，重要的还是我们要学会灵活应用。就像队列和栈一样，只要不傻的人都能轻松的理解其含义，可是真要用的时候就懵逼 了。例如如何用两个栈实现一个队列，反过来如何用两个队列实现一个栈等等。稍微扯远了，回到正题，下面简单给出在c++语言下的代码。

bool reverse(int* a,int n)//将数组a中的元素反转
{if(a==NULL)return false;int i=0,j=n-1;while(i<j){int temp=a[i];a[i++]=a[j];a[j--]=temp;}return true;
}bool exchange(int* a,int n,int swap_len)//swap_len表示交换点位置，n表示数组长度
{if(a==NULL)return false;bool flag_pre=reverse(a,swap_len);//flag_pre表示第一次反转是否成功bool flag_mid=reverse(a+swap_len,n-swap_len);bool flag_post=reverse(a,n);if(flag_pre && flag_mid && flag_post)return true;//若三次反转都成功，则此次手摇算法成功return false;
}

        注意上面代码之所以 稍微写的复杂一点，主要是为了使得代码鲁棒性更佳。写代码时考虑边界条件和特殊输入处理是一个良好的习惯。

手摇算法除了可以灵活解决字符串反转之外，还能用来优化归并排序。常规的归并排序需要额外O(n)的空间处理两个有序数组的归并。有时在面试中，面试官会问你怎样使得其空间复杂度为O(1)。如果你学过手摇算法，那么你便能犀利的解决这个问题。代码待续