溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
Knuth高效洗牌算法的示例分析，相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。
今天在做一個游戲需求的時候碰到一個問題，問題很簡單，給定75個球，編號1-75，需要保證初始化的時候位置是隨機的。
顯然，我們可以初始化一個數組A，把75個數放進去，然后做一個shuffle函數隨機交換其中的元素，這樣就是隨機的。
我準備這樣做一個shuffle，但同時也想看看golang里面是否有這樣的接口直接得到結果，看了下還真有，這個函數是rand.Perm(n)，這個函數會返回一個數組，比如我傳入75，會返回一個0-74的隨機數組。
arr := rand.Perm(75)
好奇心驅使我一探究竟，golang會用什么樣的方式實現Perm函數呢？
打開golang的源代碼，在rand.go文件中找到這個函數：
實現很簡單，然而初一看有點懵，因為沒有用到shuffle，而是一次遍歷就把事情給解決了，到底是怎么回事？
仔細分析發現，這個算法非常精巧，每次遍歷都是將當前的數i和已經在數組中的隨機一個數m[j]進行交換，最終達到了公平隨機整個數組的作用。雖然只有短短3行代碼，卻讓人有種震撼的感覺。
頓時覺得golang很NB，確實很高效。
上面這段代碼寫了4行的注釋，大概意思是說不能省去0那一次，看起來沒啥用處，但是為了照顧r隨機器中的隨機序列，還是要加上，不然可能會造成負作用，這里面和隨機種子以及此后隨機的序列有關，為了對隨機序列不產生影響保證公平性，不能省略0。
網上搜索了一下高效洗牌算法，又發現python里面也有這樣的函數，這樣寫的：
for(int i = N - 1; i >= 0 ; i -- )
swap(arr[i], arr[rand(0, i)]) // rand(0, i) 生成 [0, i] 之間的隨機整數
而這個算法的出處竟然來自于TAOCP！算法就是大名鼎鼎的 Knuth-Shuffle，即 Knuth 洗牌算法。
看似簡單的問題，竟然又扯出Knuth，大意了。
能把一件小事情做到極致的人，可以稱之為藝術家。Knuth名副其實。
最后以 Knuth 的一句話共勉：
A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.
看完上述內容，你們掌握Knuth高效洗牌算法的示例分析的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
