shuffle_in_place.js

/**
 * [费舍尔-耶茨洗牌算法](http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
 * 原地洗牌实现（直接修改原始数组顺序）
 *
 * 该算法用于生成集合的随机[排列](https://en.wikipedia.org/wiki/Permutation)。
 * 注意：此方法会通过引用直接修改原始数组顺序。
 *
 * @param {Array} x 包含一个或多个数值的样本集
 * @param {Function} [randomSource=Math.random] 可选随机数源，需返回[0,1)区间的数值
 * @returns {Array} 原数组x（已洗牌）
 * @example
 * var x = [1, 2, 3, 4];
 * shuffleInPlace(x);
 * // x将被洗牌为类似[2, 1, 4, 3]的随机排列
 */
function shuffleInPlace(x, randomSource) {
    // 支持传入自定义随机数生成器，例如使用固定种子
    // 或第三方库如[random-js](https://www.npmjs.org/package/random-js)
    randomSource = randomSource || Math.random;

    // 记录当前未洗牌元素的长度
    let length = x.length;

    // 暂存元素交换的临时变量
    let temporary;

    // 当前待交换元素的索引
    let index;

    // 当未洗牌元素存在时进行迭代
    while (length > 0) {
        // 在未洗牌区间内随机选取索引
        // 注意：length--在取值后自减实现区间收缩
        index = Math.floor(randomSource() * length--);

        // 暂存当前末端元素
        temporary = x[length];

        // 将随机选取的元素与当前末端元素交换
        x[length] = x[index];
        x[index] = temporary;
    }

    return x;
}

export default shuffleInPlace;