什么是洗牌算法

長沙7喜 2019-05-15

展開全文

作者： Great Eagle

問題

小E最近在設(shè)計一款斗地主小游戲，為了保證發(fā)到玩家手中的牌具有隨機性，小E必須對現(xiàn)實世界中的洗牌過程進行模擬。看似簡單的一個問題，卻難住了小E。

于是，小E向老師請教。

思路

點評：上面即為洗牌算法的思想，其本質(zhì)是對數(shù)組元素進行隨機重排。數(shù)組中每個元素經(jīng)過洗牌算法后落在數(shù)組某個位置上的概率是相等的，洗牌算法在牌類游戲中非常有用。我們最終將算法的時間復(fù)雜度優(yōu)化到了O（n），空間復(fù)雜度優(yōu)化到了O（1）。

代碼實現(xiàn)

下面是作者用JavaScript實現(xiàn)的代碼，僅供參考?。ńㄗh大家自己動手實現(xiàn)一遍）

//對數(shù)組中的元素進行隨機重新排列，并返回
//arr:數(shù)組
function shuffle(arr) {
    for(let i = arr.length - 1; i >= 0; i--) {
        //隨機從0-i中選擇一個下標
        let randomIndex = Math.floor(Math.random() * (i + 1));
        //將選中的元素與arr[i]交換
        let t = arr[randomIndex];
        arr[randomIndex] = arr[i];
        arr[i] = t;
    }
    //返回隨機重排后的數(shù)組
    //隨機重排過程發(fā)生在原數(shù)組上，并未產(chǎn)生新數(shù)組
    return arr;
}

溫馨提示：可左右滑動

復(fù)制代碼請前往https://blog.csdn.net/Great_Eagle/article/details/84839932