18.乱序.md

Math.Random

var values = [1, 2, 3, 4, 5];

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

console.log(values);

Math.random - 0.5 随机得到一个正数、负数或是0,如果是整数则是降序排列,如果是负数则升序排列,如果是0则不变,然后不断的升序或降序,最终得到一个乱序的数组

插入排序

v8处理sort方法时,当目标数组长度小于10,使用插入排序,反之,使用快速排序和插入排序的混合排序

v8插入排序源码:

function InsertionSort(a, from, to) {
    for (var i = from + 1; i < to; i++) {
        var element = a[i];
        for (var j = i - 1; j >= from; j--) {
            var tmp = a[j];
            var order = comparefn(tmp, element);
            if (order > 0) {
                a[j + 1] = tmp;
            } else {
                break;
            }
        }
        a[j + 1] = element;
    }
};

// ---

var values = [1, 2, 3];

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


// 此时sort函数底层使用插入排序实现
// from为0, to为3
InsertionSort(values,0,3);
// 插入排序视第一个值为有序的 所以外层循环从 i=1 开始
// a[i]的值为2,内层循环比较compare(1,2)
// 因为 Math.random() - 0.5 结果有50%概率小于0和大于0
// 所以有50%概率 变成 [2,1,3] ,50%概率不变 依然是 [1,2,3]

在插入排序算法中,当排序元素跟有序元素进行比较时,一旦确定了位置,就不会再和前面的有序元素进行进行比较,所以乱序的不彻底

Fisher–Yates

function shuffle(a) {
    var j, x, i;
    for (i = a.length; i; i--) {
        j = Math.floor(Math.random() * i);
        x = a[i - 1];
        a[i - 1] = a[j];
        a[j] = x;
    }
    return a;
}

遍历数组元素,然后将当前元素与以后随机位置的元素进行交换