1.利用数组方法sort实现随机排序
实现随机排序方法还是很多的，用for循环是可以写的，用Lodash等三方js方法库也行。但个人以为使用sort比较方便，但是他又缺点，缺点就是不够那么的随机，我看过sort运行机制后，发现他竟然是利用一个比较器两两比较出来的。
var arr = [1, 2, 3, 4, 5] arr.sort(function () { return Math.random() - 0.5 }) console.log(arr);
2.洗牌算法实现随机排序
从原始数组中每次随机选中一个元素，然后放入新数组中，每取出一个元素后，将将它从原数组中取出（使用splice方法），原数组长度减一。举例：
现在我有红桃K、黑桃A、小王三张牌，要求打乱顺序，你可以从三张牌抽出任意一张，假设你抽到的是小王，那么我手里三张牌变成两张牌，你手里变成1张牌，以此类推，实现随机排序。
代码实现：
function shuffle(array){ let res = [], random; while(array.length>0){ random = Math.floor(Math.random()*array.length); res.push(array[random]); array.splice(random, 1); } return res; } console.log(shuffle([1,2,3,4,5]));
3.洗牌算法深入分析
思路：我有一副牌，随机抽取牌，旧的牌数量相应减少! function shuffle(m) //洗牌 //抽牌法 { //生成m张牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //每次抽出一张牌，需要遍历整个数组，所以很耗时。 var arr2 = new Array(); for (var i=m; i>0; i–) { var rnd = Math.floor(Math.random()*i); arr2.push(arr[rnd]); arr.splice(rnd,1); } return arr2; } 但是这样的话，因为数组如果很大的话，删除中间的某个元素，会导致后面的数据被执行，会对性能影响很大。 我们删除那个元素的目的就是为了不产生空牌。 除了删除那个元素之外，我们是不是还有其它方式来去除空牌？ ---------------------------------------------------------------------------------- 只需把最后一张未抽的牌放在那个抽走的位置上就可以了。 顺着这个思路我们可以优化成这样： 代码如下: function shuffle_pick(m) //洗牌 //抽牌法优化牌 { //生成m张牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //每次抽出一张牌，放在另一堆。把最后一张未抽的牌放在空位子上。 var arr2 = new Array(); for (var i=m; i>0;) { var rnd = Math.floor(Math.random()*i); arr2.push(arr[rnd]); arr[rnd] = arr[–i]; } return arr2; } 除了抽牌思路，我们还可以用换牌思路： “随机交换两个位置，共交换n次，n越大，越接近随机”。 --------------------------------------------------------------------------- 顺着这个思路，做一点小调整就可以了：第i张与任意一张牌换位子，换完一轮即可。 代码如下: function shuffle_swap(m) //洗牌 //换牌法 { //生成m张牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //第i张与任意一张牌换位子，换完一轮即可 for (var i=0; i<m; i++) { var rnd = Math.floor(Math.random()*(i+1)), temp = arr[rnd]; arr[rnd] = arr[i]; arr[i]=temp; } return arr; } ------------------------------------------------------------------ 除了抽牌与换牌的思路，我们还可以用插牌的思路：先有一张牌，第二张牌有两个位置可随机插入（第一张牌前，或后），第三张牌有三个位置可随机插入（放在后面，或插在第一位，或插在第二位），依此类推 代码如下: function shuffle_insert_1(m) //洗牌 //插牌法 { //每次生成一张最大的牌，插在随机的某张牌前。因为要在数组里插入元素，把后面的所有元素向后挤一位，所以很耗时。 var arr = [0]; for (var i=1; i<m; i++) { arr.splice(Math.floor(Math.random()*(i+1)),0,i); } return arr; } -------------------------------------------------- 以上的代码也会有一些问题：就是随着牌数的增多，插牌变得越来越困难，因为插牌会导致后面的很多牌都往后推一步。 当然，我们也可以适当的优化一下：先有n-1张牌，第n张牌放在最后，然后与任意一张牌互换位置。 代码如下： function shuffle_insert(m) //洗牌 //插牌法优化版，可以用数学归纳法证明，这种洗牌是均匀的。 { //每次生成一张最大的牌，与随机的某张牌换位子 var arr = new Array(m); arr[0] = 0; for (var i=1; i<m; i++) { var rnd = Math.floor(Math.random()*(i+1)); arr[i] = arr[rnd]; arr[rnd] = i; } return arr; } ------------------------------- 最后是全部代码： 代码如下: <html> <head> <meta http-equiv=”Content-Type” content=”text/html; charset=gb2312″> <title>JK：javascript 洗牌算法 </title> </head> <body> <script type=”text/javascript”> function shuffle_pick_1(m) //洗牌 //抽牌法 { //生成m张牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //每次抽出一张牌，放在另一堆。因为要在数组里抽出元素，把后面的所有元素向前拉一位，所以很耗时。 var arr2 = new Array(); for (var i=m; i>0; i–) { var rnd = Math.floor(Math.random()*i); arr2.push(arr[rnd]); arr.splice(rnd,1); } return arr2; } function shuffle_pick(m) //洗牌 //抽牌法优化牌 { //生成m张牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //每次抽出一张牌，放在另一堆。把最后一张未抽的牌放在空位子上。 var arr2 = new Array(); for (var i=m; i>0;) { var rnd = Math.floor(Math.random()*i); arr2.push(arr[rnd]); arr[rnd] = arr[–i]; } return arr2; } function shuffle_swap(m) //洗牌 //换牌法 { //生成m张牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //第i张与任意一张牌换位子，换完一轮即可 for (var i=0; i<m; i++) { var rnd = Math.floor(Math.random()*(i+1)), temp = arr[rnd]; arr[rnd] = arr[i]; arr[i]=temp; } return arr; } function shuffle_insert_1(m) //洗牌 //插牌法 { //每次生成一张最大的牌，插在随机的某张牌前。因为要在数组里插入元素，把后面的所有元素向后挤一位，所以很耗时。 var arr = [0]; for (var i=1; i<m; i++) { arr.splice(Math.floor(Math.random()*(i+1)),0,i); } return arr; } function shuffle_insert(m) //洗牌 //插牌法优化版，可以用数学归纳法证明，这种洗牌是均匀的。 { //每次生成一张最大的牌，与随机的某张牌换位子 var arr = new Array(m); arr[0] = 0; for (var i=1; i<m; i++) { var rnd = Math.floor(Math.random()*(i+1)); arr[i] = arr[rnd]; arr[rnd] = i; } return arr; } //alert(shuffle_pick(10)) var funcs = [shuffle_pick_1, shuffle_pick, shuffle_swap, shuffle_insert_1, shuffle_insert], funcNames = [“抽牌”, “抽牌优化”, “换牌”, “插牌”, “插牌优化”] m = 10000, times=[]; for(var i = 0; i < funcs.length; i++){ var d0= new Date(); funcs[i](m); funcNames[i] = (new Date() – d0) + ‘\t’ + funcNames[i]; } alert(funcNames.join(‘\n’)); </script> </body> </html>
