洗牌算法的实现

写在前面

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

题目要求

假如给你一个数组

    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,证明我们成功的写出了正确的答案！

写在后面

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