豕の家

相信太难,不如沉默来得简单

算法  Knuth-Durstenfeld Shuffle洗牌算法
March 31, 2021 / 22:32 / 30 °C

shuffle

下面是用JS实现的shuffle算法

function shuffle(arr){
  let n=arr.length;
  for(let i=0;i<n;i++){
    let t=arr[i];
    let r=Math.floor(Math.random()*(n-i)+i);
    arr[i]=arr[r];
    arr[r]=t;
  }
}

let arr=[1,3,2,5,8,0];
for(let k=0;k<5;k++){
  shuffle(arr);
  console.log(arr);  
}

/*
    这段可以测试[0,9]的每个整数取到的概率是否平均
*/
// let q=[0,0,0,0,0,0,0,0,0,0,];
// let e=0;
// let x=0,y=9;
// for(let i=0;i<100000;i++){
//   e=Math.floor(Math.random()*10);
//   q[e]++;
// }
// for(let k=0;k<10;k++){
//   console.log(`${k}:`+q[k]);
// }

*注意一定要用Math.floor而不是round函数,具体可以见:这篇文章

导航栏中的“混串”也就是shuffle算法,当时看到总是有人把打乱语序当成梗来玩,所以就去查了下具体是什么算法实现的。





© Posted By @shawnt

Comment

称呼:  
邮箱:  
网址: