洗牌演算法是什么？
其實就理解為生成一個亂數列的一個簡單操作而已，
怎么生成？
我們先講下一般我們會想到的一個解法——標記，
怎么標記呢？
假設我們的陣列為a，ai 代表陣列a第i個數，
一個布爾陣列b（其他型別的陣列也行），
然后把a陣列下標作為狀態空間進行隨機生成，接著把生成過的數下標 i 用 bi =1表示為已出現過，用 bi==0表示為未出現過.
如果前面出現過的數則重新隨機，
問題來了：這樣的復雜度是多少？——會是n2的復雜度，如果平均下來也是n log n
所以怎么處理這個問題？
如果你想洗掉當前數的話——洗掉會導致陣列整體向后移動啊！
相信大家都學過二叉堆（沒學過也沒事），更新數值時我們會把堆頂放在堆末尾，然后再UP，DOWN操作一遍，
類比一下——這樣避免了整個陣列的往后移動，
假設最初陣列里1~N個數需要隨機，目前隨機范圍為N
所以我們可以生成完當前數后，把這個數和最后一個數交換，然后隨機下標范圍變為N-1
以此回圈即可，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/421634.html
標籤：其他
上一篇：大廠面試：一個四年多經驗程式員的BAT面經（位元組、阿里、騰訊）
下一篇：WebGPU 的幾個最佳實踐