1.???背景
阿里的面試的時(shí)候做的一道筆試題:
題目：寫一個(gè)方法,入?yún)樽匀粩?shù)n? (n > 0)，返回一個(gè)自然數(shù)數(shù)組，數(shù)組長度為n，元素為[1,n]之間，且每個(gè)元素不重復(fù)，數(shù)組中各元素順序要求隨機(jī)；
實(shí)例1： 輸入: N = 3? 輸出: 132
實(shí)例2： 輸入: N = 5? ?輸出: 32514
當(dāng)時(shí)我的解法（寫了兩種方法）：
寫的好爛，面完和面試官交流的時(shí)候面試官讓我看下Collections.shuffle的源碼，于是乎就開始研究這個(gè)“洗牌算法”。
2.洗牌算法
洗牌就是將原有的排序打亂的一個(gè)過程，我們可以通過抽牌、換牌和插牌三種方式進(jìn)行洗牌。最常用的洗牌算法：即Fisher-Yates Shuffle和Knuth-Durstenfeld Shhuffle，我們分別學(xué)習(xí)一下兩種洗牌算法。
2.1 Fisher-Yates Shuffle ?
所述費(fèi)舍爾-耶茨洗牌是一種算法：用于產(chǎn)生隨機(jī)排列的有限的序列，簡單地說，該算法對序列進(jìn)行洗牌。
算法的自然語言描述為（給定1到N的序列）：
①記下從1到N的數(shù)字。
②從1到結(jié)尾的未刪除數(shù)字（包括）之間選擇一個(gè)隨機(jī)數(shù)k。
③從低端開始計(jì)數(shù)，剔除尚未剔除的第k個(gè)數(shù)字，并將其寫下一個(gè)單獨(dú)的列表的末尾。
④從第2步開始重復(fù)，直到所有數(shù)字都被刪除。
⑤現(xiàn)在在步驟3中寫下的數(shù)字序列就是原始序列的隨機(jī)排列。
理論上的費(fèi)舍爾-耶茨洗牌算法的時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度O(n)。
2.2 Knuth-Durstenfeld?Shuffle
所述克努斯-杜斯騰菲爾德算法是一個(gè)現(xiàn)代版的費(fèi)舍爾-耶茨算法，我們實(shí)現(xiàn)Fisher和Yates算法時(shí)會花費(fèi)不必要的時(shí)間來用來計(jì)算上面第3步中的剩余數(shù)字，但Durstenfeld的解決方案是將“刪除”的數(shù)字移到列表的末尾，然后將每個(gè)被刪除的數(shù)字交換為最后一個(gè)未刪除的數(shù)字迭代，簡言之：每次迭代時(shí)交換這個(gè)被取出的數(shù)字到原始列表的最后。這將算法的時(shí)間復(fù)雜度從O(n2)降低到了O(n)。
偽代碼實(shí)現(xiàn)：
//To shuffle an arraya?ofn?elements? (indices? 0...n-1):
for?i?from?n?1down to?1do?
?j?← random integer such that 0 ≤j?≤i?exchangea[j] anda[i]
按照上述的偽代碼的描述，我們使用JS實(shí)現(xiàn)這段偽代碼：
算法需要的時(shí)間正比于要隨機(jī)置亂的數(shù)，不需要額為的存儲空間開銷，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度O(1)。
3. Collections.shuffle()
源碼解析：
傳入待洗牌的List集合，定義一個(gè)隨機(jī)數(shù)種子。
獲取集合的長度，其中SHUFFLE_THRESHOLD = 5，當(dāng)list的長度<5或者list實(shí)現(xiàn)了RandomAccess接口的時(shí)候，通過倒序的循環(huán)交換索引位置與隨機(jī)生成的[0,i)的索引位置。
當(dāng)集合長度>5的時(shí)候，將集合轉(zhuǎn)為數(shù)組，然后再次進(jìn)行隨機(jī)值交換，然后將數(shù)組重新set到集合里面去，這樣做避免了將“順序訪問”列表洗牌到適當(dāng)?shù)奈恢枚鴮?dǎo)致的二次行為。
主意事項(xiàng)：
1）用List<Integer> list=ArrayList(Arrays.asList(ia))，用shuffle()打亂不會改變底層數(shù)組的順序。
2）用List<Integer> list=Arrays.aslist(ia)，然后用shuffle()打亂會改變底層數(shù)組的順序。
可以使用洗牌算法實(shí)現(xiàn)掃雷。
