完美洗牌算法简析与代码实现 |
您所在的位置：网站首页 › 洗牌算法时间复杂度是什么 › 完美洗牌算法简析与代码实现 |
完美洗牌算法简析与代码实现
|
题目需求 数组[a1,a2,a3,a4,b1,b2,b3,b4]，洗牌后变成[b1,a1,b2,a2,b3,a3,b4,a4]。 不得使用额外的空间，即空间复杂度要求为O(1)。因为如果用线性空间，直接变成2个链表归并就行，特别简单。 算法思路 1）定义与约定 数组长度为2n，下标i从1开始计数，且i的范围[1,2n]。 2）算法思路 公式 1）i->(2*i)%(2n+1) 理解，第i个元素值替换到第(2*i)%(2n+1)个元素，依此类推，直到完成一圈代换 2）2^n=3^k-1 理解，当长度正好为3^k-1时，数组恰好可以切分为k个环，没有多余元素 3）3^k 理解，环头。环的起始位置为1、3、9、27等3的指数位置算法 1）将数组分成2个部分，前一部分正好是3^k-1个元素 2）对前一部分进行环代换算法 3）对剩余的部分，递归调用当前算法 算法理解 1）为什么能切分数组为2个部分然后再洗牌并递归
假设2m=3^k-1。则洗牌后前一半(前n个元素)中的前m个元素与后一半(后n个元素)中的前m个元素占据着前2m个槽位。那么，我们可以在洗牌之前提前先将这2m个元素放在一起。即预处理后A1区块与A2区块是挨着的，B1区块与B2区块是挨着的，因为我们知道洗牌后A1与A2共同占用前2m个槽位，B1与B2共同占用后2n-2m个槽位。预处理后排列如下图所示。
有了这个前提之后，我们就可以先将整个数组重新排一下，排成上图所示的样子，其中A1与A2组成的部分就可以直接用圈代换算法，将所有的元素都洗牌好。对于剩下的B1与B2组成的部分，再递归调用前面的算法。 2）如何交互A2与B1并保证其原来的顺序用循环称位即可将B1按原来的顺序移动到A2前面，且A2与B1均保持原来的内部顺序。具体就是将A2B1视为一个整体，然后循环右移B1区块的长度即可。 循环移位算法，直接移位效率比较低，可以用两次局部逆序与一次整体逆序来实现。即 这个算法，主要也就是圈头位置，恰好被分割为若干个圈的数组长度两部分内容，国外专门有一篇论文讲这个just in-place代换，有一些数学推理与证明在里面，具体感兴趣的可以去研究下。：）此处就不多提。 代码实现 #ifndef SHUFFLE_H #define SHUFFLE_H #include #include #include "common.h" template class Shuffle { public: Shuffle(const std::vector& vec); /** * @brief rightCycleMove right shift a array * @param start start position,included * @param stop stop position,not include * @param num right shift number */ static void rightCycleMove(typename std::vector::iterator start, typename std::vector::iterator stop,unsigned int num); /** * @brief reverse reverse the span * @param start start position * @param stop stop position, not include */ static void reverse(typename std::vector::iterator start,typename std::vector::iterator stop); /** * @brief findRightShiftPos find the length (2^n)=log3(K)-1 * @param start start position * @param stop stop position * @param pos length (2^n) * @return find or not */ static bool findRightShiftPos (typename std::vector::iterator start,typename std::vector::iterator stop,unsigned int & pos); /** * @brief splitInto2Part split array into 2 part,one is in perfect length,the remain we can recursivie * @param start * @param stop * @param middle split position * @return */ static bool splitInto2Part(typename std::vector::iterator start, typename std::vector::iterator stop, typename std::vector::iterator &middle); /** * @brief shuffle recursive function,split into 2 part, exchange perfect part, and recursive * @param start * @param stop * @return */ static bool shuffle(typename std::vector::iterator start,typename std::vector::iterator stop); /** * @brief shuffle shuffle function for object * @return */ bool shuffle(); std::vector getData() const{return m_vecData__;} private: std::vector m_vecData__; ///< data tobe shuffle }; template Shuffle::Shuffle(const std::vector &vec) { m_vecData__=vec; } template void Shuffle::reverse(typename std::vector::iterator start, typename std::vector::iterator stop) { typename std::vector::iterator l,r; l=start; r=stop; r--; for(;l |
【本文地址】