数组乱序

发表于 | 分类于 | 阅读次数:

sort()

利用传入sort排序中的比较函数，比较的规则如下：

  • 如果compareFunc(a,b)的返回值小于0，那么a会被排到b之前；
  • 如果compareFucn(a,b)的返回值等于0，那么a和b的相对位置不变；
  • 如果compareFunc(a,b)的返回值大于0，那么b会被拍到a之前。

代码如下：

1
2
3
4
5
6
function randomSort(arr){
    arr.sort(function(a,b){
        return Math.random() - 0.5;
    });
    return arr
}

ES6写法：

1
2
3
4
5
6
function randomSort(arr){
    arr.sort((a,b)=>{
        return Math.random() - 0.5;
    });
    return arr;
}

这种写法的平均时间复杂度是O(nlogn)。

Fisher–Yates shuffle(洗牌算法)

为了便于理解，数组下标假设从1开始。

原始算法（O(n²)）

  1. 给定一个数组arr，数组内的元素为已排好序的1-N的数字
  2. 产生一个随机数k，范围为1 -（N），取出并将arr[k]放在数组最后
  3. 继续产生随机数k，范围为1 -（N-1），取出并将arr[k]放在数组最后
  4. 以此类推，直到所有数字都被取出。

现代算法（O(n)）

  1. 给定一个数组arr，数组内的元素为已排好序的1-N的数字
  2. 产生一个随机数k，范围为1 -（N），取出并将arr[k-1]放在数组最后，并将剩下元素中的最后一个元素（arr[N]）放在arr[k]的位置。
  3. 继续产生随机数k，范围为1 -（N-1），取出并将arr[k-1]放在数组最后，并将剩下元素中的最后一个元素（arr[N-1]）放在arr[k]的位置。
  4. 以此类推，直到所有数字都被取出。

举个例子：

给定数组[1,2,3,4,5,6,7,8]。

随机数范围 随机数 原始数据 结果
[1,2,3,4,5,6,7,8]
1-8 6 [1,2,3,4,5,6,7,8] [1,2,3,4,5,8,7, 6]
1-7 2 [1,2,3,4,5,8,7] [1,7,3,4,5,8, 2,6]
1-6 1 [1,7,3,4,5,8] [8,7,3,4,5, 1,2,6]
1-5 4 [8,7,3,4,5] [8,7,3,5, 4,1,2,6]
1-4 1 [8,7,3,5] [5,7,3, 8,4,1,2,6]
1-3 2 [5,7,3] [5,3, 7,8,4,1,2,6]
1-2 1 [5,3] [3, 5,7,8,4,1,2,6]

代码如下：

1
2
3
4
5
6
7
8
9
10
11
Array.prototype.shuffle = function() {
    let input = this;
    for (var i = input.length-1; i >=0; i--) {
        let randomIndex = Math.floor(Math.random()*(i+1));
        let itemAtIndex = input[randomIndex];
        input[randomIndex] = input[i];
        input[i] = itemAtIndex;
    }
    return input;
}
[1,2,3,4,5,6,7,8].shuffle()

Referebce

费希尔 - 耶茨洗牌

Fisher–Yates shuffle 洗牌算法