0
Perfect Shuffle 的算法
source link: https://zhiqiang.org/cs/another-perfect-shuffle-algorithm.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Perfect Shuffle 的算法
珍爱生命，远离政治。我们继续讨论算法。
2008/04/01 补充：此算法有重大缺陷。详情请见留言部分。
一年前，我们讨论过一个算法问题， perfect shuffle ，据称是个微软面试题：
输入a1,a2,⋯,an,b1,⋯,bna1,a2,⋯,an,b1,⋯,bn ，如何用O(n)O(n) 的时间，O(1)O(1) 的空间，将这个序列顺序改为a1,b1,⋯,an,bna1,b1,⋯,an,bn 。
那一次讨论我们翻出了问题的来源，一篇长达 12 页的论文Computing the Cycles in the Perfect Shuffle Permutation，算法那是非常的复杂，我估计贴出来都没几个人仔细看。
这一次， Xie Xie （没错，又是他 :) ）翻出了 Art of Computer Programming, Volume 3 上的一个难度为 40 分的 Merge Sort 习题：
已知数列x1≤x2≤⋯xM,xM+1≤xM+2≤⋯≤xnx1≤x2≤⋯xM,xM+1≤xM+2≤⋯≤xn ，设计算法使得在线性时间，常数空间实现归并，也就是将原数组排序。
而 Perfect Shuffle 问题是可以规约到这个 Merge Sort 问题的：
mergeSort(x[1...2n]); // if this function solve Merge Sort problem
perfectShuffle(x[1...2n]): // then this solve Perfect Shuffle problem
m <- max(x[1...2n])+1;
x[i] <- x[i]+(2i-1)m,
x[i+n] <- x[i+n] + 2im
mergeSort(x[1...2n])
x[i] <- x[i]%m
原来我还不相信这个问题会是一个面试题。现在我信了。因为那个归并排序的算法还是有些牛人会知道的。
很好很强大。
Q. E. D.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK