实现数组乱序有以下三种方式:
直接在 sort 函数里面传入一个乱序的 function
- let arr = [2, 3, 1, 5, 4];
- arr.sort(() => {
- return Math.random()> 0.5
- // 上面这行如果返回 true 则表示两个元素交换位置, 为 false 则表示两个元素不交换位置
- })
存在的问题: 如果每两个元素之间都有机会碰面, 都有 0.5 的概率进行交换的话就可以实现乱序, 但是实际 sort 函数里面并不是所有的元素之间都可以碰面的, 例如在 JS 的 sort 函数底层是通过插入排序和快速排序实现的, 但是在排序过程中, 并不是所有的元素之间都可以碰面的, 这也导致了这种乱序方法不可能实现完全的乱序
将原数组进行改造, 把数组的每一项改造成对象, 对象的 val 字段设为数组原来该位置的值, 同时设置一个 ram 字段, 存储一个随机数, 然后对 ram 字段进行升序或是降序排序, 就可以实现数组的完全乱序了
- let arr = [2, 3, 1, 5, 4];
- // 先对原数组进行转化
- const arr_obj = arr.map(val => {
- return { val, ram: Math.random() };
- })
- // 对转化后的数组针对 ram 字段进行排序
- arr_obj.sort((a, b) => {
- return a.ram> b.ram
- })
- // 再次改造数组
- const final_arr = arr_obj.map(item => item.val)
从上面的操作可以发现这种方法虽然可以实现完全的乱序, 但是缺点在于时间复杂度较高, 首先需要多次遍历数组对数组进行改造, 其次还是需要对数组进行一次排序, 这次排序的复杂度是 O(nlogn)~O(n^2) 数量级的, 所以时间复杂度高
FIsher-yates 方法, 时间复杂度为 O(n), 只需要对数组进行一次从后往前的遍历即可实现数组的完全乱序
- let arr = [2, 3, 1, 5, 4];
- let len = arr.length;
- for(let i = len - 1; i> 0; i--) {
- let index = i * Math.random();
- [arr[i], arr[index]] = [arr[index], arr[i]];
- }
来源: http://www.jianshu.com/p/28629cc41062