js打乱数组的实战应用

蚊子前端博客
发布于 2019-04-06 23:15
在js中,能把数组随机打乱的方法有很多,每个方法都有自己的哪些特点呢,同时若想随机取出数组中的几个元素,怎么办呢?

在js中,能把数组随机打乱的方法有很多,每个方法都有自己的特点。

1. 打乱数组的方法

这里主要讲解3个打乱数组的方法。

1.1 随机从数组中取出数据

这个方法的详细操作步骤是:随机从数组中取出一个数组放入到新数组中,然后将该数据从原数组中删除,然后再随机取出下一个数,直到原数据的长度为0。

COPYJAVASCRIPT

function randomArrByOut(arr) { let result = []; let arrTemp = [...arr]; // splice会影响原数组,复制一个新的数组,防止影响原数组 while(arrTemp.length) { let index = Math.floor(Math.random() * arrTemp.length); result.push(arrTemp[index]); arrTemp.splice(index, 1); } return result; } let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]; randomArrByOut(arr); // [7, 1, 3, 8, 2, 4, 6, 5, 9] randomArrByOut(arr); // [8, 4, 3, 7, 9, 2, 1, 5, 6]

这个算法看似是O(n)的算法,但实际上arr.splice内部是一个O(n^2)的算法Array.prototype.splice的内部实现:外部循环用来删除元素,内部的循环用来填充新添加的元素,或后面的元素向前移动,填充刚才被删除的元素的坑。总的算下来,这个算法的时间复杂度就是O(n^3)了。

1.2 sort方法打乱

还有一种常见的方法就是使用数组自带的sort方法来打算数组,sort方法是直接修改当前的数组:

COPYJAVASCRIPT

function randomSortBySort(arr) { arr.sort(() => Math.random() - 0.5); }

当前环节里所有的测试均在Chrome中。当我们使用9个数据,经过多次的测试发现,打乱的数据排布并不均匀:

COPYJAVASCRIPT

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]; var n = 10000; var count = {}; while(n--) { randomSortBySort(arr); var index = arr.indexOf(1); count[index] ? count[index]++ : (count[index] = 1); } console.log(count); /* 数据1经过10000次打乱后的分布规律,主要集中在前2个 0: 2047 1: 1403 2: 947 3: 822 4: 777 5: 822 6: 992 7: 1008 8: 1182 */

我们再把arr的数组扩展为15,再进行测试:

COPYJAVASCRIPT

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]; var n = 10000; var count = {}; while(n--) { randomSortBySort(arr); var index = arr.indexOf(1); count[index] ? count[index]++ : (count[index] = 1); } console.log(count); // {0: 668, 1: 647, 2: 652, 3: 665, 4: 692, 5: 652, 6: 679, 7: 657, 8: 665, 9: 683, 10: 685, 11: 690, 12: 662, 13: 663, 14: 640}

可以发现每次打乱后的分布比较均匀,每个数字出现在每个位置的机会都是均等的!

V8的源码中L710行中可以看到:

COPYJAVASCRIPT

function InnerArraySort( array, length, comparefn ) { // In-place QuickSort algorithm. // For short (length <= 22) arrays, insertion sort is used for efficiency. // 虽然注释是length<=22,但代码里是<=10 // 插入排序 var InsertionSort = function InsertionSort( a, from, to ) { }; var QuickSort = function QuickSort( a, from, to ) { var third_index = 0; while ( true ) { // Insertion sort is faster for short arrays. if ( to - from <= 10 ) { InsertionSort( a, from, to ); return; } // 快排其他的内容 } } QuickSort(array, 0, num_non_undefined); }

sort的内部使用快速排序,当快排拆分后的分区里的数据个数小于等于10个时,则采用插入排序!因此,当数据量比较小的时候,使用sort打乱排序时,会造成不均等的分布!

1.3 洗牌算法

最后一个经典的数组打乱算法就是洗牌算法:从最后一个数据开始往前,每次从前面随机一个位置,将两者交换,直到数组交换完毕:

COPYJAVASCRIPT

function shuffleSort(arr) { var n = arr.length; while(n--) { var index = Math.floor(Math.random() * n); var temp = arr[index]; arr[index] = arr[n]; arr[n] = temp; // ES6的解耦交换方式: [arr[index], arr[n]] = [arr[n], arr[index]]; } }

这种方式是O(n)的时间复杂度,而且还能保证一个比较均匀的分布!高效了很多

2. 从数组中随机取出多个元素

这是从数组中随机取出几个元素,上面的一节是将整个数组进行排序,而这里只是需要几个元素而已!

2.1 打乱整个数组取出数据

当然,先把整个数组打乱了,然后再取出前n个数据也是其中的一种方法,比如我们这里就使用洗牌算法打乱数组,然后取出数据:

COPYJAVASCRIPT

function getRandomArr(arr, num) { var _arr = arr.concat(); var n = _arr.length; // 先打乱数组 while(n--) { var index = Math.floor(Math.random() * n); [_arr[index], _arr[n]] = [_arr[n], _arr[index]]; } return _arr.slice(0, num); }

不过实际上我们只是需要其中的几个元素而已,如果把整个数组都打乱排序,就显得很浪费。因此这里我们使用洗牌算法的思路,稍微改进一下。

2.2 改进型

从最后一个数据开始往前,每次从前面随机一个位置,将两者交换,拿到最后的那个数据,直到达到要获取的个数:

COPYJAVASCRIPT

function getRandomArr(arr, num) { var _arr = arr.concat(); var n = _arr.length; var result = []; // 先打乱数组 while(n-- && num--) { var index = Math.floor(Math.random() * n); // 随机位置 [_arr[index], _arr[n]] = [_arr[n], _arr[index]]; // 交换数据 result.push(_arr[n]); // 取出当前最后的值,即刚才交换过来的值 } return result; }

3. 总结

数组中还是有很多的学问的,看看其中的源码,也会发现更多的奥妙!

标签:
阅读(858) 评论(0)

公众号:

qrcode

微信公众号:前端小茶馆