除了其他答案,這比簡單的費希爾耶茨洗牌更糟糕,因爲它太慢了。 qsort算法是O(n * log(n)),Fisher-Yates是O(n)。
一些細節可以在維基百科上,爲什麼這種「洗牌」一般不工作,以及the Fisher-Yates method:
與其他洗牌 算法
費雪耶茨洗牌是比較相當有效率的 ;的確,其漸近時間 和空間複雜度是最佳的。 結合隨機數字來源的高質量不偏不倚 ,它也是 保證產生公正的 結果。相比於其他一些 解決方案,它還有一個優點 ,如果只需要所產生的 置換的一部分,它可以 需要中途停止過,甚至 停止並反覆重啓, 產生置換 增量。在高級別 具有快速 編程語言內置排序算法, 另一種方法,其中每個元素的集合的 要混洗的被分配 隨機數和該組是然後 根據這些數字排序,儘管 漸近時間複雜度(O(n log n) 與O(n))相比,儘管 在實踐中可能更快[需要引用 ]。像費雪耶茨洗牌 ,這種方法也會產生 公正的結果,如果正確實施 ,也可以是某些類型的偏見的更加寬容 在隨機 數字。但是,必須注意 以確保所分配的隨機 號碼從不重複,因爲 排序算法通常不會 以 爲條件隨機排列元素。已經看到在語言 一些使用支持與 用戶指定的比較函數排序上述方法 的一個變體是 通過與返回 隨機值的 比較函數排序它洗牌列表。但是,這並不是 始終工作:與一些通常使用排序算法0,結果 最終偏向由於內部 不對稱的排序 實施。[7]
此鏈接到here:當我寫這篇 文章中,我嘗試了各種 版本的方法和原來的版本 發現 多了一個瑕疵
還有一件事(由我改名到shuffle_sort
)。我 錯了,當我說:「它返回一個很好 洗牌陣列每次它是 調用的時候。」
結果不是很好的洗牌在 所有。他們有偏見。厲害。 意味着元素的一些排列(即 排序)比其他排列更可能是 。下面是 另一個代碼片段來證明這一點,從 再次借新聞組討論:
N = 100000
A = %w(a b c)
Score = Hash.new { |h, k| h[k] = 0 }
N.times do
sorted = A.shuffle
Score[sorted.join("")] += 1
end
Score.keys.sort.each do |key|
puts "#{key}: #{Score[key]}"
end
此代碼 洗牌100,000次陣3個 要素:A,B,C和記錄多少 次每個可能的結果是 實現。在這種情況下,只有 六個可能的排序,我們應該 每個約16666.66次。如果 我們嘗試的shuffle
(shuffle
或shuffle_sort_by
)一個不帶偏見的版本, 結果是如預期:
abc: 16517
acb: 16893
bac: 16584
bca: 16568
cab: 16476
cba: 16962
當然, 存在一些偏差,但他們 不應超過 期望值的幾個百分比,並且他們應該是 每次我們運行此代碼都會有所不同。 甚至可以說分配是 。
好的,如果我們使用 shuffle_sort方法會發生什麼?
abc: 44278
acb: 7462
bac: 7538
bca: 3710
cab: 3698
cba: 33314
這不是 均勻分佈在所有。再次?
它顯示了排序方法是如何偏離的,並詳細說明了爲什麼如此。最後,他鏈接到Coding Horror:
讓我們來看看正確的 克努特 - 費雪耶茨洗牌算法。
for (int i = cards.Length - 1; i > 0; i--)
{
int n = rand.Next(i + 1);
Swap(ref cards[i], ref cards[n]);
}
你看到的區別?我第一次錯過了 。比較互換 對於3張牌:
Naïve shuffle Knuth-Fisher-Yates shuffle
rand.Next(3); rand.Next(3);
rand.Next(3); rand.Next(2);
rand.Next(3);
天真洗牌 結果在3^3(27)可能的甲板 組合。這很奇怪,因爲 數學告訴我們,有 真的只有3!或者3張牌組合的6個可能的 組合。在KFY洗牌 ,我們從一個初始的 訂單開始,從第三個位置 與這三張卡中的任何一個交換,然後再從第二個位置交換 與 剩下的兩張卡。
該變化使情況變得更糟,現在函數永遠不會返回equ先進而精湛。 – Juliano 2009-04-26 02:02:40
我以爲你可以自由選擇一個或其他的平等... – ojblass 2009-04-26 02:08:25