洗牌算法

出處：https://mp.weixin.qq.com/s/uYPnZ0MsQIT2_t3lk8ju1g

問題

小E最近在設計一款鬥地主小遊戲，為了保證發到玩家手中的牌具有随機性，小E必須對現實世界中的洗牌過程進行模拟。看似簡單的一個問題，卻難住了小E。

于是，小E向老師請教。

思路

點評：上面即為洗牌算法的思想，其本質是對數組元素進行随機重排。數組中每個元素經過洗牌算法後落在數組某個位置上的機率是相等的，洗牌算法在牌類遊戲中非常有用。我們最終将算法的時間複雜度優化到了O（n），空間複雜度優化到了O（1）。

java代碼實作：

import java.util.Random;

public class Test4 {

    public static void main(String[] args) {
        int[] datas = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,12,  13, 14, 15, 16, 17, 18, 19, 20};
        int[] returnDatas = shuffle(datas);
        System.out.println("nums:"+ returnDatas.length);
        for(int i = 0, length = returnDatas.length; i < length; i++) {
            System.out.print(returnDatas[i]+", ");
        }
    }
    
    public static int[] shuffle(int[] nums) {
        Random rnd = new Random();
        for(int i = nums.length-1; i > 0; i-- ) {
            int j = rnd.nextInt(i+1);
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        return nums;
    }

}      

輸出資訊：

nums:20

6, 9, 18, 10, 2, 16, 7, 19, 14, 1, 12, 5, 3, 4, 17, 20, 8, 15, 13, 11,