09月08, 2016

javascript随机函数

随机取一个值: 一般情况下代码逻辑放在后端处理,前端只负责展现。 但是若是若是后端不愿意做,e...那么前端需要能够实现。

需求:实现一个数组的打乱重拍。若是直接从数组中随机取一个值比较简单,直接var item = items[Math.floor(Math.random()*items.length)]得到一个随机值。下面看怎么对数组进行重新排序。

so ... 遇到问题第一步,先查查网上有木有已经实现的比较好的方式~ Fisher-Yates binggo!

Fisher-Yates乱序算法

思路,假如你要洗牌,那么最随机的做法就是从牌堆里随便抽一张出来,然后放在一边,之后从剩下的牌里重复之前的操作,直到所有牌都被抽出来放到另外一堆中。

round 1


随机从数组里取出一个元素,保存到另一个数组,然后重复之,直到原数组中所有元素为空。 查看演示

function shuffle(array) {
    var copy = [],
        n = array.length,
        i;
    // 如果还剩有元素则继续。。。
    while (n) {
        // 随机抽取一个元素
        i = Math.floor(Math.random() * array.length);
        // 如果这个元素之前没有被选中过。。
        if (i in array) {
            copy.push(array[i]);
            delete array[i];
            n--;
        }
    }
    return copy;
}

问题:我们新建一个数组,每次都会随机取一个0-len的随机值,随机值可能一样;另外一方面可能永远运行不完。

注: Math.random()产生[0,1)的小数 delete 操作只将数组元素的值删除,但不影响数组长度,删除后原来位置的值变为undefined

round 2


用Array的splice()方法将其从目标数组中移除同时也更新了目标数组的长度,如此一来下次遍历的时候是从新的长度开始,不会重复处理的情况了。 查看演示

function shuffle(array) {
    var copy = [],
        n = array.length,
        i;
    // 如果还剩有元素。。
    while (n) {
        // 随机选取一个元素
        i = Math.floor(Math.random() * n--);
        // 移动到新数组中
        copy.push(array.splice(i, 1)[0]);
    }
    return copy;
}

round 3


因为调用splice来删除数组元素会导致删除位置之后的所有元素要做shift操作来向前补充,从而达到将数组长度减小的目的,当然这是在后台自动完成的,但这无疑增加了算法的复杂度。

注意到我们要做的仅仅是将数组元素重新排序,已经取出来的元素和剩下的元素之和一定是等于数组原来的总元素个数的。所以可以考虑不创建新的数组来保存已经抽取的元素,可以这样,随机从数组中抽出一个元素,然后与最后个元素交换,相当于把这个随机抽取的元素放到了数组最后面去,表示它已经是被随机过了,同时被换走的那个元素跑到前面去了,会在后续的重复操作中被随机掉。一轮操作过后,下一轮我们只在剩下的n-1个元素也就是数组的前n-1个元素中进行相同的操作,直到进行到第一个。 查看演示

function shuffle(array) {
    var m = array.length,
        t, i;
    // 如果还剩有元素…
    while (m) {
        // 随机选取一个元素…
        i = Math.floor(Math.random() * m--);
        // 与当前元素进行交换
        t = array[m];
        array[m] = array[i];
        array[i] = t;
    }
    return array;
}

不急,还有一个,真是简洁。但是随机效果不好。

round 4


function shuffle(array) {
    return array.sort(function() {
        return Math.random() - 0.5
    });
}

⬆️ 这厮有bug! 在IE 11上。sort方法的返回值应该是0,1,-1。这里返回true和false。 所以,改进之后:

function shuffle(array) {
    return array.sort(function() {
        return Math.random() > 0.5 ? 1: -1;
    });
}

生成一个1-len的数组。

  • Array.from(Array(len).keys()); //返回[0-length]的数组
  • Math.pow(2, len).toString(2).split('').map((i,j) => j);
  • Array(N).fill().map((_, i) => i + 1);
  • Array.from(Array(5)).map((_, i) => i + 1);

本文链接:http://westpsk.com/post/js-sort.html

-- EOF --

Comments