阅读 802

洗牌算法的实现

写在前面

相信大家都写过很多排序算法,但是你对乱序算法熟悉吗?现在就让小白带你走进乱序算法的世界。

题目要求

力扣地址

假如给你一个数组

    let arr = [0,1,2,3,4,5,6,7,8,9]
复制代码

请问你如何将这个数组随机打乱输出?

错误的解法

    console.log(arr.sort(() => Math.random() - 0.5));
复制代码

乍一看,这个解法好像没什么问题,我们得到的结果好像也都是正确的,但是它真的是随机的吗?

随机的真正含义

首先,我们需要理解在这道题目中随机的真正含义是什么?随机的真正含义应该是每个数字,在每个位置出现的几率都相等。也就是说,0在这十个位置中出现的几率是相等的,1在这十个位置中出现的几率是相等的......

为何上面的解法有问题

对于上面的解法, 我们姑且用伪随机来称呼它。首先,我们先看看sort()方法在 MDN中的解释:


arr.sort([compareFunction]) compareFunction 可选

  • 用来指定按某种顺序进行排列的函数。如果省略,元素按照转换为的字符串的各个字符的Unicode位点进行排序。
  • firstEl 第一个用于比较的元素。
  • secondEl 第二个用于比较的元素。

  • 我的理解
    • a,b 表示正在进行比较的两个数
    • a-b 小于 0 ,那么 a 会被排列到 b 之前
    • a-b 等于 0 , a 和 b 的相对位置不变
    • a-b 大于 0 ,那么 a 会被排列到 b 之后
console.log(arr.sort((a, b) => a - b)); // 升序
console.log(arr.sort((a, b) => b - a)); // 降序
复制代码

如果上面的解法是正确的的,那么,如果我们随机10000次,每个位置上加起来的数的平均数应该约等于4.5,我们试验一下:

let arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
let res = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
function shuffle(arr) {
    return arr.sort(() => Math.random() - 0.5)
}
let t = 10000;
for (let i = 0; i < t; i++) {
    // 对数组先进行浅拷贝
    let sorted = shuffle(arr.slice(0));
    for (let i = 0; i < sorted.length; i++) {
        res[i] = sorted[i] + res[i];
    }
}
console.log(res.map(sum => sum / t));
复制代码

这里每次对数组进行浅拷贝是为了保证每次随机的都是原数组。 多运行几次后输出:

我们发现出现了3.8,5.1这样的极端情况,这明显是不符合随机的定义的。那么是哪里出错了呢?

  • arr.sort(() => Math.random() - 0.5)
  • 这里的含义是设置 两个数交换的概率为50%。也就是说,两个数可能交换也可能不交换,这明显不符合随机的定义。

正确的解法

如果我们将比较的两个数 100% 交换,那么我们是不是达到了随机的要求了呢?在这里我采用了洗牌算法。 代码如下:

let arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
let res = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
function shuffle(arr) {
    let len = arr.length;
    for (let i = 0; i < len; i++) {
        // -i 从后面
        // 从前面随机取一个数的下标
        // Math.floor(x) 返回小于等于x的最大整数 向下取整
        let idx = Math.floor(Math.random() * (len - i));
        [arr[len - 1 - i], arr[idx]] = [arr[idx], arr[len - 1 - i]];
    }
    return arr;
}
let t = 10000;
for (let i = 0; i < t; i++) {
    // 对数组先进行浅拷贝
    let sorted = shuffle(arr.slice(0));
    for (let i = 0; i < sorted.length; i++) {
        res[i] = sorted[i] + res[i];
    }
}
console.log(res.map(sum => sum / t));
复制代码
  • 思路
    • 我们从后往前取一个基准数 a
    • 然后从未洗牌的区间随机取一个数b(a也在未洗牌的区域内)
    • a b 交换
    • 从后往前 重复上述步骤
  • 验证结果

可以看到此时我们的结果已经趋向于4.5,证明我们成功的写出了正确的答案!

写在后面

此前在网上看到了这道题,笔者觉得挺有意思, 特意来与大家分享下,希望大家都能成功解决这道算法题。 笔者目前是一名大三学生,正在学习前端的有关知识,对于算法的理解也不是很透彻,如果有相应问题,欢迎指正。希望可以和大家一起成长!

关注下面的标签,发现更多相似文章
评论