# 数组的完全随机排列

Array.prototype.sort 方法被许多 JavaScript 程序员误用来随机排列数组。最近做的 前端星计划 挑战项目中，一道实现 blackjack 游戏的问题，就发现很多同学使用了 Array.prototype.sort 来洗牌。就连最近一期 JavaScript Weekly 上推荐的 一篇文章 也犯了同样的错误。

``function shuffle(arr){     return arr.slice(0).sort(function(){         return Math.random() - 0.5;     }); } ``

## 证明 Array.prototype.sort 随机算法的错误

``var arr = [0,1,2,3,4,5,6,7,8,9]; var res = [0,0,0,0,0,0,0,0,0,0];  var t = 10000; for(var i = 0; i < t; i++){   var sorted = shuffle(arr);   sorted.forEach(function(o,i){       res[i] += o;   }); }  res = res.map(function(o){     return o / t; });  console.log(res); ``

``function bubbleSort(arr, compare){     for(var i = 0; i < arr.length; i++){         for(var j = i; j < arr.length; j++){             if(compare(arr[i], arr[j]) > 0){                 var tmp = arr[i];                   arr[i] = arr[j];                   arr[j] = tmp;             }         }     }     return arr; }  function shuffle(arr){     return bubbleSort(arr, function(){         return Math.random() - 0.5;     }); }  var arr = [0,1,2,3,4,5,6,7,8,9]; var res = [0,0,0,0,0,0,0,0,0,0];  var t = 10000; for(var i = 0; i < t; i++){   var sorted = shuffle(arr);   sorted.forEach(function(o,i){       res[i] += o;   }); }  res = res.map(function(o){     return o / t; });  console.log(res); ``

``function quickSort(arr, compare){   arr = arr.slice(0);   if(arr.length <= 1) return arr;   var mid = arr[0], rest = arr.slice(1);   var left = [], right = [];    for(var i = 0; i < rest.length; i++){       if(compare(rest[i], mid) > 0){       right.push(rest[i]);     }else{       left.push(rest[i]);     }   }    return quickSort(left, compare).concat([mid])   .concat(quickSort(right, compare)); }  function shuffle(arr){     return quickSort(arr, function(){         return Math.random() - 0.5;     }); }  var arr = [0,1,2,3,4,5,6,7,8,9]; var res = [0,0,0,0,0,0,0,0,0,0];  var t = 10000; for(var i = 0; i < t; i++){   var sorted = shuffle(arr);   sorted.forEach(function(o,i){       res[i] += o;   }); }  res = res.map(function(o){     return o / t; });  console.log(res); ``

## 快速的随机排列

``function shuffle(arr){       var len = arr.length;     for(var i = 0; i < len - 1; i++){         var idx = Math.floor(Math.random() * (len - i));           var temp = arr[idx];           arr[idx] = arr[len - i - 1];           arr[len - i -1] = temp;     }       return arr; } ``

``function shuffle(arr){       var len = arr.length;     for(var i = 0; i < len - 1; i++){         var idx = Math.floor(Math.random() * (len - i));           var temp = arr[idx];           arr[idx] = arr[len - i - 1];           arr[len - i -1] = temp;     }       return arr; }  //console.log(shuffle2([1,2,3,4,5,6,7,8,9]));  var arr = [0,1,2,3,4,5,6,7,8,9]; var res = [0,0,0,0,0,0,0,0,0,0];  var t = 10000; for(var i = 0; i < t; i++){   var sorted = shuffle(arr);   sorted.forEach(function(o,i){       res[i] += o;   }); }  res = res.map(function(o){     return o / t; });  console.log(res); ``

### 随机性的数学归纳法证明

1. 首先我们考虑 n = 2 的情况，根据算法，显然有 1/2 的概率两个数交换，有 1/2 的概率两个数不交换，因此对 n = 2 的情况，元素出现在每个位置的概率都是 1/2，满足随机性要求。

2. 假设有 i 个数， i >= 2 时，算法随机性符合要求，即每个数出现在 i 个位置上每个位置的概率都是 1/i。

3. 对于 i + 1 个数，按照我们的算法，在第一次循环时，每个数都有 1/(i+1) 的概率被交换到最末尾，所以每个元素出现在最末一位的概率都是 1/(i+1) 。而每个数也都有 i/(i+1) 的概率不被交换到最末尾，如果不被交换，从第二次循环开始还原成 i 个数随机，根据 2. 的假设，它们出现在 i 个位置的概率是 1/i。因此每个数出现在前 i 位任意一位的概率是 `(i/(i+1)) * (1/i) = 1/(i+1)` ，也是 1/(i+1)。

4. 综合 1. 2. 3. 得出，对于任意 n >= 2，经过这个算法，每个元素出现在 n 个位置任意一个位置的概率都是 1/n。