数组-乱序

数组乱序指的是：将数组元素的排列顺序随机打乱

日常开发中，”洗牌“或”换一批“等场景下可能会用到。

思路一：

利用sort中的特性：compareFunction(a, b) 必须总是对相同的输入返回相同的比较结果，否则排序的结果将是不确定的。MDN (opens new window)

理想情况下，一个洗牌算法，希望数组中每两个元素都要进行比较，这两就可以触发交换的逻辑，而是否交换则是random出来的，也就是50%概率交换，50%概率不交换； 然而实际情况是，不管用什么排序方法，元素之间的比较次数通常也都是远小于 n(n-1)/2 的，也就意味着有一些元素之间根本就没机会相比较（也就没有了随机交换的可能），这些 sort 随机排序的算法自然也不能真正随机。

所以我们会看到测试结果中，所有元素大概率停留在自己初始位置。究其原因，在Chrome v8引擎源码中，可以清晰看到，

v8使用了插入排序和快排两种方案。 当目标数组长度小于10时，使用插入排序；反之，使用快速排序。

为什么要用两种算法实现呢？ 首先数组元素如果小于 10 时采用插入排序，插入排序在最好的情况下为 O(n)，当 n 很小时插入排序是有着很高的性能的，甚至是会超过快排的。 这是因为 QuickSort 在分区后需要递归调用两次，这个过程会产生函数栈空间的创建、销毁开销。插入排序随着 n 变大也会退化为 O(n^2)。

• 1.直接利用sort进行排序，有漏洞，大部分元素位置没有移动

function shuffle(arr) {
  return arr.sort(() => (Math.random() > 0.5)); // 
}

• 2.Fisher–Yates算法：就是将数组从后向前遍历，然后将当前元素与随机位置的元素进行交换

- 
function shuffle(arr=[]){
    for (let i = arr.length - 1; i > 0; i--) {
        let ranIndex = Math.floor(Math.random() * i);
        [arr[ranIndex],arr[i]] = [arr[i],arr[ranIndex]];
    }
    return arr;
}

• 验证shuffle是否完全随机

/**
* 用于验证 shuffle 方法是否完全随机
*/
function test_shuffle(shuffle) {
    
    // 保存每个元素在每个位置上出现的次数
    let countObj = {};
    for (let i = 1; i <= 10; i++) {
        countObj[i] = [0,0,0,0,0,0,0,0,0,0];
    }

    // 开始测试 
    for (let i = 1; i <= 10000; i++) { // 来10000次
        let arr = [1,2,3,4,5,6,7,8,9,10] // 测试len为10的数组
        shuffle(arr);
        for (let j = 1; j <= 10; j++) {
            countObj[j][arr.indexOf(j)]++;
        }
    }
    console.table(countObj);
}
test_shuffle(shuffle)

参考 (opens new window) 透过 v8 源码看 sort 方法的实现原理 (opens new window) 为什么使用sort()不是真正意义的乱序呢？ (opens new window)