題目詳情

有個長度為2n的數組{a1,a2,a3,...,an,b1,b2,b3,...,bn}，希望排序后{a1,b1,a2,b2,....,an,bn}，請考慮有無時間復雜度o(n)，空間復雜度0(1)的解法。

題目來源：此題是去年2013年UC的校招筆試題，看似簡單，按照題目所要排序后的字符串蠻力變化即可，但若要完美的達到題目所要求的時空復雜度，則需要我們花費不小的精力。OK，請看下文詳解，一步步優化。

分析與解法

解法一、蠻力變換

題目要我們怎么變換，咱們就怎么變換。此題@陳利人也分析過，在此，引用他的思路進行說明。為了便于分析，我們取n=4，那么題目要求我們把

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

變成

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

1.1、步步前移

仔細觀察變換前后兩個序列的特點，我們可做如下一系列操作：

第①步、確定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)，我們得繼續尋找其它方法，看看有無辦法能達到題目所預期的O(N)的時間復雜度。

1.2、中間交換

當然，除了如上面所述的讓b1，b2，b3，b4步步前移跟它們各自前面的元素進行交換外，我們還可以每次讓序列中最中間的元素進行交換達到目的。還是用上面的例子，針對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

同樣，此法同解法1.1、步步前移一樣，時間復雜度依然為O(N^2)，我們得下點力氣了。

解法二、完美洗牌算法

玩過撲克牌的朋友都知道，在一局完了之后洗牌，洗牌人會習慣性的把整副牌大致分為兩半，兩手各拿一半對著對著交叉洗牌，如果這副牌用a1 a2 a3 a4 b1 b2 b3 b4表示(為簡化問題，假設這副牌只有8張牌)，然后一分為二之后，左手上的牌可能是a1 a2 a3 a4，右手上的牌是b1 b2 b3 b4，那么在如上圖那樣的洗牌之后，得到的牌就可能是b1 a1 b2 a2 b3 a3 b4 a4。

技術來源于生活，2004年，microsoft的Peiyush Jain在他發表一篇名為：“A Simple In-Place Algorithm for In-Shuffle”的論文中提出了完美洗牌算法。

這個算法解決一個什么問題呢？跟本題有什么聯系呢？

Yeah，顧名思義，完美洗牌算法解決的就是一個完美洗牌問題。什么是完美洗牌問題呢？即給定一個數組a1,a2,a3,...an,b1,b2,b3..bn,最終把它置換成b1,a1,b2,a2,...bn,an。讀者可以看到，這個完美洗牌問題本質上與本題完全一致，只要在完美洗牌問題的基礎上對它最后的序列swap兩兩相鄰元素即可。

即：

a1,a2,a3,...an,b1,b2,b3..bn

通過完美洗牌問題，得到：

b1,a1,b2,a2,b3,a3... bn,an

再讓上面相鄰的元素兩兩swap，即可達到本題的要求：

a1,b1,a2,b2,a3,b3....,an,bn

也就是說，如果我們能通過完美洗牌算法(時間復雜度O(N)，空間復雜度O(1))解決了完美洗牌問題，也就間接解決了本題。

雖然網上已有不少文章對上篇論文或翻譯或做解釋說明，但對于初學者來說，理解難度實在太大，再者，若直接翻譯原文，根本無法看出這個算法怎么一步步得來的，故下文將從完美洗牌算法的最基本的原型開始說起，以讓讀者能對此算法一目了然。

2.1、位置置換pefect_shuffle1算法

為方便討論，我們設定數組的下標從1開始，下標范圍是[1..2n]。 還是通過之前n=4的例子，來看下每個元素最終去了什么地方。

起始序列：a1 a2 a3 a4 b1 b2 b3 b4 數組下標：1 2 3 4 5 6 7 8 最終序列：b1 a1 b2 a2 b3 a3 b4 a4

從上面的例子我們能看到，前n個元素中， > 第1個元素a1到了原第2個元素a2的位置，即1->2； > 第2個元素a2到了原第4個元素a4的位置，即2->4； > 第3個元素a3到了原第6個元素b2的位置，即3->6； > 第4個元素a4到了原第8個元素b4的位置，即4->8； >

那么推廣到一般情況即是：前n個元素中，第i個元素去了 第(2 * i)的位置。

上面是針對前n個元素，那么針對后n個元素，可以看出： > 第5個元素b1到了原第1個元素a1的位置，即5->1； > 第6個元素b2到了原第3個元素a3的位置，即6->3； > 第7個元素b3到了原第5個元素b1的位置，即7->5； > 第8個元素b4到了原第7個元素b3的位置，即8->7；

推廣到一般情況是，后n個元素，第i個元素去了第 (2 (i - n) ) - 1 = 2i - (2 n + 1) = (2i) % (2 * n + 1) 個位置。

再綜合到任意情況，任意的第i個元素，我們最終換到了 (2 i) % (2n + 1)的位置。為何呢？因為： > 當0 < i < n時， 原式= (2i) % (2 n + 1) = 2i； > 當i > n時，原式(2i) % (2 * n + 1)保持不變。

因此，如果題目允許我們再用一個數組的話，我們直接把每個元素放到該放得位置就好了。也就產生了最簡單的方法pefect_shuffle1，參考代碼如下：

但很明顯，它的時間復雜度雖然是O(n)，但其空間復雜度卻是O(n)，仍不符合本題所期待的時間O(n)，空間O(1)。我們繼續尋找更優的解法。

與此同時，我也提醒下讀者，根據上面變換的節奏，我們可以看出有兩個圈， > 一個是1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1；

一個是3 -> 6 -> 3。

下文2.2.1、走圈算法cycle_leader將再次提到這兩個圈。

2.2、完美洗牌算法perfect_shuffle2

2.2.1、走圈算法cycle_leader

因為之前perfect_shuffle1算法未達到時間復雜度O(N)并且空間復雜度O(1)的要求，所以我們必須得再找一種新的方法，以期能完美的解決本節開頭提出的完美洗牌問題。

讓我們先來回顧一下2.1節位置置換perfect_shuffle1算法，還記得我之前提醒讀者的關于當n=4時，通過位置置換讓每一個元素到了最后的位置時，所形成的兩個圈么？我引用下2.1節的相關內容：

當n=4的情況：

起始序列：a1 a2 a3 a4 b1 b2 b3 b4

數組下標：1 2 3 4 5 6 7 8

最終序列：b1 a1 b2 a2 b3 a3 b4 a4

即通過置換，我們得到如下結論：

“于此同時，我也提醒下讀者，根據上面變換的節奏，我們可以看出有兩個圈， > 一個是1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1；

一個是3 -> 6 -> 3。”

這兩個圈可以表示為(1,2,4,8,7,5)和(3,6)，且perfect_shuffle1算法也已經告訴了我們，不管你n是奇數還是偶數，每個位置的元素都將變為第(2*i) % (2n+1)個元素：

因此我們只要知道圈里最小位置編號的元素即圈的頭部，順著圈走一遍就可以達到目的，且因為圈與圈是不相交的，所以這樣下來，我們剛好走了O(N)步。

還是舉n=4的例子，且假定我們已經知道第一個圈和第二個圈的前提下，要讓1 2 3 4 5 6 7 8變換成5 1 6 2 7 3 8 4：

第一個圈：1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1 第二個圈：3 -> 6 -> 3：

原始數組：1 2 3 4 5 6 7 8 數組下標：1 2 3 4 5 6 7 8

走第一圈：5 1 3 2 7 6 8 4 走第二圈：5 1 6 2 7 3 8 4

上面沿著圈走的算法我們給它取名為cycle_leader，這部分代碼如下：

2.2.2、神級結論：若2*n=(3^k - 1)，則可確定圈的個數及各自頭部的起始位置

下面我要引用此論文“A Simple In-Place Algorithm for In-Shuffle”的一個結論了，即 對于2*n = (3^k-1)這種長度的數組，恰好只有k個圈，且每個圈頭部的起始位置分別是1,3,9，...3^(k-1)。

論文原文部分為：也就是說，利用上述這個結論，我們可以解決這種特殊長度2*n = (3^k-1)的數組問題，那么若給定的長度n是任意的咋辦呢？此時，我們可以采取分而治之算法的思想，把整個數組一分為二，即拆分成兩個部分：

讓一部分的長度滿足神級結論：若2*m = (3^k-1)，則恰好k個圈，且每個圈頭部的起始位置分別是1,3,9，...3^(k-1)。其中m < n，m往神級結論所需的值上套；

剩下的n-m部分單獨計算；

當把n分解成m和n-m兩部分后，原始數組對應的下標如下(為了方便描述，我們依然只需要看數組下標就夠了)：

原始數組下標：1..m m+1.. n， n+1 .. n+m, n+m+1,..2*n

且為了能讓前部分的序列滿足神級結論2*m = (3^k-1)，我們可以把中間那兩段長度為n-m和m的段交換位置，即相當于把m+1..n，n+1..n+m的段循環右移m次(為什么要這么做？因為如此操作后，數組的前部分的長度為2m，而根據神級結論：當2m=3^k-1時，可知這長度2m的部分恰好有k個圈)。

而如果讀者看過本系列第一章、左旋轉字符串的話，就應該意識到循環位移是有O(N)的算法的，其思想即是把前n-m個元素(m+1.. n)和后m個元素(n+1 .. n+m)先各自翻轉一下，再將整個段(m+1.. n， n+1 .. n+m)翻轉下。

這個翻轉的代碼如下：

翻轉后，得到的目標數組的下標為：

目標數組下標：1..m n+1..n+m m+1 .. n n+m+1,..2*n

OK，理論講清楚了，再舉個例子便會更加一目了然。當給定n=7時，若要滿足神級結論2*n=3^k-1，k只能取2，繼而推得n‘=m=4。

原始數組：a1 a2 a3 a4 a5 a6 a7 b1 b2 b3 b4 b5 b6 b7

既然m=4，即讓上述數組中有下劃線的兩個部分交換，得到：

目標數組：a1 a2 a3 a4 b1 b2 b3 b4 a5 a6 a7 b5 b6 b7

繼而目標數組中的前半部分a1 a2 a3 a4 b1 b2 b3 b4部分可以用2.2.1、走圈算法cycle_leader搞定，于此我們最終求解的n長度變成了n’=3，即n的長度減小了4，單獨再解決后半部分a5 a6 a7 b5 b6 b7即可。

2.2.3、完美洗牌算法perfect_shuffle3

從上文的分析過程中也就得出了我們的完美洗牌算法，其算法流程為： > 輸入數組　A[1..2 n] > step 1 找到 2m = 3^k - 1 使得 3^k <= 2 n < 3^(k +1) > step 2 把a[m + 1..n + m]那部分循環移m位 > step 3 對每個i = 0,1,2..k - 1，3^i是個圈的頭部，做cycle_leader算法，數組長度為m，所以對2m + 1取模。 > step 4 對數組的后面部分A[2 m + 1.. 2n]繼續使用本算法, 這相當于n減小了m。

上述算法流程對應的論文原文為：

以上各個步驟對應的時間復雜度分析如下： > 因為循環不斷乘3的，所以時間復雜度O(logn) > 循環移位O(n) > 每個圈，每個元素只走了一次，一共2*m個元素，所以復雜度omega(m), 而m < n，所以 也在O(n)內。 T(n - m) > 因此總的時間復雜度為 T(n) = T(n - m) + O(n) ，m = omega(n) ，解得：T(n) = O(n)。

此完美洗牌算法實現的參考代碼如下：

2.2.4、perfect_shuffle2算法解決其變形問題

啊哈！以上代碼即解決了完美洗牌問題，那么針對本章要解決的其變形問題呢？是的，如本章開頭所說，在完美洗牌問題的基礎上對它最后的序列swap兩兩相鄰元素即可，代碼如下：

上述的這個“在完美洗牌問題的基礎上對它最后的序列swap兩兩相鄰元素”的操作(當然，你也可以讓原數組第一個和最后一個不變，中間的2 * (n - 1)項用原始的標準完美洗牌算法做)，只是在完美洗牌問題時間復雜度O(N)空間復雜度O(1)的基礎上再增加O(N)的時間復雜度，故總的時間復雜度O(N)不變，且理所當然的保持了空間復雜度O(1)。至此，咱們的問題得到了圓滿解決！

問題擴展

神級結論是如何來的？

我們的問題得到了解決，但本章尚未完，即決定完美洗牌算法的神級結論：若2*n=(3^k - 1)，則恰好只有k個圈，且每個圈頭部的起始位置分別是1,3,9，...3^(k-1)，是如何來的呢？要證明這個結論的關鍵就是：這所有的圈合并起來必須包含從1到M之間的所有正數，一個都不能少。這個證明有點麻煩，因為證明過程中會涉及到群論等數論知識，但再遠的路一步步走也能到達。

首先，讓咱們明確以下相關的概念，定理，及定義(搞清楚了這些東西，咱們便證明了一大半)： > 概念1 mod表示對一個數取余數，比如3 mod 5 =3，5 mod 3 =2； > 定義1 歐拉函數(m) 表示為不超過m(即小于等于m)的數中，與m互素的正整數個數 > 定義2 若(m)=Ordm(a) 則稱a為m的原根，其中Ordm(a)定義為：a ^d ( mod m)，其中d=0,1,2,3…，但取讓等式成立的最小的那個d。

結合上述定義1、定義2可知，2是3的原根，因為2^0 mod 3 = 1, 2^1 mod 3 = 2, 2^2 mod 3 = 1, 2^3 mod 3 = 2，{a^0 mod m，a^1 mod m，a^2}得到集合S={1,2}，包含了所有和3互質的數，也即d=(2)=2，滿足原根定義。

而2不是7的原根，這是因為2^0 mod 7 = 1, 2^1 mod 7 = 2, 2^2 mod 7 = 4, 2^3 mod 7 = 1，2^4 mod 7 = 2，2^5 mod 7 = 4，2^6 mod 7 = 1，從而集合S={1,2,4}中始終只有1、2、4三種結果，而沒包含全部與7互質的數(3、6、5便不包括),，即d=3，但(7)=6，從而d != (7)，不滿足原根定義。

再者，如果說一個數a，是另外一個數m的原根，代表集合S={a^0modm,a^1modm,a^2modm……}，得到的集合包含了所有小于m并且與m互質的數，否則a便不是m的原根。而且集合S={a^0modm,a^1modm,a^2modm……}中可能會存在重復的余數，但當a與m互質的時候，得到的{a^0modm,a^1modm,a^2modm}集合中，保證了第一個數是a^0modm，故第一次發現重復的數時，這個重復的數一定是1，也就是說，出現余數循環一定是從開頭開始循環的。>定義3對模指數，a對模m的原根定義為,st:中最小的正整數d

再比如，2是9的原根，因為，為了讓除以9的余數恒等于1，可知最小的正整數d=6，而(m)=6，滿足原根的定義。>定理1同余定理：兩個整數a，b，若它們除以正整數m所得的余數相等，則稱a，b對于模m同余，記作，讀做a與b關于模m同余。>定理2當p為奇素數且a是的原根時a也是的原根>定理3費馬小定理：如果a和m互質，那么a^(m)modm=1>定理4若(a,m)=1且a為m的原根，那么a是(Z/mZ)*的生成元。

取a = 2, m = 3。

我們知道2是3的原根，2是9的原根，我們定義S(k)表示上述的集合S，并且取x = 3^k(x表示為集合S中的數)。

所以：S(1) = {1, 2} S(2) = {1, 2, 4, 8, 7, 5}

我們沒改變圈元素的順序，由前面的結論S(k)恰好是一個圈里的元素，且認為從1開始循環的，也就是說從1開始的圈包含了所有與3^k互質的數。

那與3^k不互質的數怎么辦？如果0 < i < 3^k與 3^k不互質，那么i 與3^k的最大公約數一定是3^t的形式(只包含約數3)，并且 t < k。即gcd(i , 3^k) = 3^t，等式兩邊除以個3 ^ t，即得gcd( i/(3^t)，3^(k - t) ) = 1， i/(3^t) 都與3^(k - t) 互質了，并且i / (3^t) < 3^(k - t), 根據S(k)的定義，可見i/(3^t) 在集合S(k - t)中。

同理，任意S(k - t)中的數x，都滿足gcd(x , 3^k) = 1,于是gcd(3^k , x3^t) = 3 ^ t, 并且x3^t < 3^k。可見S(k - t)中的數x*3^t 與 i形成了一一對應的關系。

也就是說S(k - t)里每個數x* 3^t形成的新集合包含了所有與3^k的最大公約數為3^t的數，它也是一個圈,原先圈的頭部是1，這個圈的頭部是3^t。

于是，對所有的小于 3^k的數，根據它和3^k的最大公約數，我們都把它分配到了一個圈里去了，且k個圈包含了所有的小于3^k的數。

下面，舉個例子，如caopengcs所說，當我們取“a = 2, m = 3時，

我們知道2是3的原根，2是9的原根，我們定義S(k)表示上述的集合S，并且x= 3^k。

所以

S(1) = {1, 2}

S(2) = {1, 2, 4, 8, 7, 5}

比如k = 3。 我們有：

S(3) = {1, 2 ,4 , 8, 16, 5, 10, 20, 13, 26, 25, 23, 19, 11, 22, 17, 7, 14} 包含了小于27且與27互質的所有數，圈的首部為1，這是原根定義決定的。

那么與27最大公約數為3的數，我們用S(2)中的數乘以3得到。 S(2) * 3 = {3, 6, 12, 24, 21, 15}, 圈中元素的順序沒變化，圈的首部是3。

與27最大公約數為9的數，我們用S(1)中的數乘以9得到。 S(1) * 9 = {9, 18}, 圈中得元素的順序沒變化，圈的首部是9。

因為每個小于27的數和27的最大公約數只有1, 3, 9這3種情況，又由于前面所證的一一對應的關系，所以S(2) 3包含了所有小于27且與27的最大公約數為3的數，S(1)9 包含了所有小于27且和27的最大公約數為9的數。”

換言之，若定義為整數，假設/N定義為整數Z除以N后全部余數的集合，包括{0...N-1}等N個數，而(/N)*則定義為這Z/N中{0...N-1}這N個余數內與N互質的數集合。

則當n=13時，2n+1=27，即得/N =｛0,1,2,3,.....,26}，(/N)*相當于就是｛0,1,2,3,.....,26}中全部與27互素的數的集合；

而2^k(mod 27)可以把(/27)*取遍，故可得這些數分別在以下3個圈內：

取頭為1，(/27)*＝｛1,2,4,8,16,5,10,20,13,26,25,23,19,11,22,17,7,14｝，也就是說，與27互素且小于27的正整數集合為{1,2,4,8,16,5,10,20,13,26,25,23,19,11,22,17,7,14}，因此(m)=(27)=18,從而滿足的最小d=18，故得出2為27的原根；

取頭為3，就可以得到｛3,6,12,24,21,15｝，這就是以3為頭的環，這個圈的特點是所有的數都是3的倍數，且都不是9的倍數。為什么呢？因為2^k和27互素。

具體點則是：如果3×2^k除27的余數能夠被9整除，則有一個n使得32^k=9n(mod 27)，即32^k－9n能夠被27整除，從而3*2^k－9n＝27m，其中n，m為整數，這樣一來，式子約掉一個3，我們便能得到2^k＝9m＋3n，也就是說，2^k是3的倍數，這與2^k與27互素是矛盾的，所以，3×2^k除27的余數不可能被9整除。

此外，2^k除以27的余數可以是3的倍數以外的所有數，所以，2^k除以27的余數可以為1,2,4,5,7,8，當余數為1時，即存在一個k使得2^k-1=27m，m為整數。

式子兩邊同時乘以3得到：32^k-3=81m是27的倍數，從而32^k除以27的余數為3；

同理，當余數為2時，2^k - 2 = 27m，=> 32^k- 6 =81m，從而32^k除以27的余數為6；

當余數為4時，2^k - 4 = 37m，=> 32^k - 12 =81m，從而32^k除以27的余數為12；

同理，可以取到15，21，24。從而也就印證了上面的結論：取頭為3，就可以得到｛3,6,12,24,21,15｝。 取9為頭，這就很簡單了，這個圈就是｛9,18}

你會發現，小于27的所有自然數，要么在第一個圈里面，也就是那些和27互素的數；要么在第二個圈里面，也就是那些是3的倍數，但不是9的倍數的數；要么在第三個圈里面，也就是是9倍數的數，而之所以能夠這么做，就是因為2是27的本原根。證明完畢。

最后，咱們也再驗證下上述過程：

因為，故：

i = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

由于n=13，2n+1=27，據此公式可知，上面第i位置的數將分別變成下述位置的：

i = 2 4 6 8 10 12 14 16 18 20 22 24 26 1 3 5 7 9 11 13 15 17 19 21 23 25 0

根據i 和 i‘ 前后位置的變動，我們將得到3個圈：

沒錯，這3個圈的數字與咱們之前得到的3個圈一致吻合，驗證完畢。

舉一反三

至此，本章開頭提出的問題解決了，完美洗牌算法的證明也證完了，是否可以止步了呢？OH，NO！讀者有無思考過下述問題：

1、既然完美洗牌問題是給定輸入：a1,a2,a3,……aN,b1,b2,b3,……bN，要求輸出：b1,a1,b2,a2,……bN,aN；那么有無考慮過它的逆問題：即給定b1,a1,b2,a2,……bN,aN,，要求輸出a1,a2,a3,……aN,b1,b2,b3,……bN ？

2、完美洗牌問題是兩手洗牌，假設有三只手同時洗牌呢？那么問題將變成：輸入是a1,a2,……aN, b1,b2,……bN, c1,c2,……cN，要求輸出是c1,b1,a1,c2,b2,a2,……cN,bN,aN，這個時候，怎么處理？

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的java 洗牌_java数组之完美洗牌算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。