本文共 1717 字,大约阅读时间需要 5 分钟。
// 方法2:随机抽取法, 时间复杂度 O(n^2)function randomSortArray(arr) { var stack = []; while (arr.length) { //Math.random():返回 [0,1) 之间的一个随机数 var index = parseInt(Math.random() * arr.length); // 利用数组长度生成随机索引值 stack.push(arr[index]); // 将随机索引对应的数组元素添加到新的数组中 arr.splice(index, 1); // 删除原数组中随机生成的元素 } return stack;}var arr = [1, 2, 3, 4, 5, 6];var res = randomSortArray(arr);console.log(res); // [ 5, 2, 4, 6, 3, 1 ]
原理:主要是将数组里的索引值随机打乱,然后将当前的索引值与随机变化之后的索引值互换。
1.首先遍历的开始是从最大的索引开始,然后逐次递减;
2.然后选取一个随机值randomIndex,这个随机值的产生是在0-len(即数组的长度)之间产生,由于这个值不能为len(因为数组的索引是从0开始的),只能为len-1,故只能向下取整Math.floor;
3.取到随机值之后,将这个随机值对应的数组值即arr[randomIndex]赋值给当前遍历的i对应的数组值即arr[i];
// 方法3:时间复杂度 O(n)function randomSortArray2(arr) { var len = arr.length; //首先从最大的数开始遍历,之后递减 for(var i = len - 1; i >= 0; i--) { var randomIndex = Math.floor(Math.random() * (i + 1)); //随机索引值randomIndex是从0-arr.length中随机抽取的,因为Math.floor()方法是向下取整的,所以这里是i+1 //下面三句相当于把从数组中随机抽取到的值与当前遍历的值互换位置 var temp = arr[randomIndex]; arr[randomIndex] = arr[i]; arr[i] = temp; } //每一次的遍历都相当于把从数组中随机抽取(不重复)的一个元素放到数组的最后面 return arr;}var arr = [1, 2, 3, 4, 5, 6];var res = randomSortArray2(arr);console.log(res); // [ 1, 3, 5, 2, 4, 6 ]
sort 是对数组进行排序,每次从数组里面挑选两个数 进行运算。
接下来用刚才的较大数字跟下一个进行比较。这样循环进行排序。
我们利用 Math.random-0.5,这个运算的结果要么是大于0,要么是小于0.这样要么交换位置,要么不交换位置。当然大于或者小于0是随即出现的。所以数组就被随即排序了。function shuffle(arr) { arr.sort(function () { return Math.random() - 0.5; });}
或者使用更简洁的 ES6 的写法:
function shuffle(arr) { arr.sort(() => Math.random() - 0.5);}
转载地址:http://ynuvi.baihongyu.com/