-1

可能重复:
如何随机化 javascript 数组?

我需要从一个数组中实现一个随机二叉搜索树(R-BST),以便排序后的数组给出 O(n lg n) 平均时间,而不是 O(n^2) ,如果数组是最坏的情况时间已经排序或反向排序。现在两个步骤是:

  1. 随机排列数组 A。
  2. 调用 BST 排序 (A) 。

我该如何进行第一步 JavaScript?我希望它使每个n!排列都同样可能发生。我相信在 Java 中做到这一点的方法是Collections.shuffle这样说:

Integer[] arr = new Integer[10]; 

for (int i = 0; i < arr.length; i++) { 
    arr[i] = i; 
} 

Collections.shuffle(Arrays.asList(arr)); 

for (int i = 0; i < arr.length; i++) { 
    System.out.print(arr[i] + " "); 
} 

我将如何在 Javascript 中执行此操作?我可以使用 jQuery。

4

2 回答 2

1

只需.sort与随机比较器一起使用:

var comparer = function(a,b) {
    return 2 * Math.random() - 1;
}
array.sort( comparer );

编辑由于有些人对解决方案不满意,所以这里有更经典的方法:

Array.prototype.shuffle = function() {
    var result = [];
    while( this.length ) {
        var index = Math.floor( this.length * Math.random() );
        result.push( this[ index ] );
        this.splice(index, 1);
    }
    return result;
};
于 2012-08-20T08:19:05.177 回答
-1

您可以使用 shuffle 函数扩展 Array 原型:

Array.prototype.shuffle = function() {
  var tmp, rand;
  for(var i =0; i < this.length; i++){
    rand = Math.floor(Math.random() * this.length);
    tmp = this[i]; 
    this[i] = this[rand]; 
    this[rand] = tmp;
  }
}

然后调用shuffle任何数组进行就地排序:

var arr = [1,2,3,4];
arr.shuffle();
console.log(arr);
于 2012-08-20T08:17:46.987 回答