那些代码量很少却很牛X算法——洗牌算法
阅读本文前，请您先点击上面的蓝色字体“Android扫地僧”，“关注”后再点击星标，及时上车，优质干货，重磅资源第一时间送达。
首先，出一个简单的题目：有一个大小为100的数组，里面的元素是从 1 到 100，怎样随机从里面选择 1 个数呢？
很简单，利用 Math.random() * 100 ，就可以拿到一个 0 到 99 的随机数，然后去数组找对应的位置就行了。
下面难度提高一点哈！ 有一个大小为100的数组，里面的元素是从 1 到 100，怎样随机从里面选择 50 个数呢？注意！不能重复。
如果根据上面的思路，你一定想到了：是不是随机 50 次就行了？
那么问题来了，这 50 次你是不能保证都是不能重复的，对吧！
嗯，你是不是又有灵感了，弄一个数组，把每一次随机的数都放到数组里，下一次随机就看这个数组里面有没有这数，有的话就继续随机，直到这个数组里面有 50 个数字就停止。完美！
嗯，讲道理的话，这样做也没有问题，肯定可以实现题目要求。但是如果我们想一下，就会发现问题：如果我们考虑极限，就比如拿 99 个数字（你不要跟我说：那就考虑相反的情况，拿 1 个数字，把这个数字去掉就行>。< ），是不是越往后重复的概率越高，那么需要重复随机的次数也越大？
是的，小老弟，你很聪明，一下子就理解了。我们可以看下代码：
var idxArr = []while(idxArr.length < 99){
let idx = parseInt(Math.random()*100)
var time = 0
while(idxArr.includes(idx)) {
idx = parseInt(Math.random()*100)
console.log('time', time++)
}
idxArr.push(idx);}
代码很简单，如果随机的数字不在数组里面，就 push 进去，否则就重新随机。这里用了一个 times 来计算每一个数需要随机的次数。可以看下输出：
image
image
可以看到，一开始基本是没有重复的，但是到了后面最后一个，要拿到一个没有出现过的随机数需要多达 65 次。
如果你把数组再放大一点，结果会更加夸张。当然，现实里不会有这么极端的情况，就像你说的，要拿 99 个数就反过来剔除 1 个数就行了。但是呢，就算没有 99 也可能有 50 对吧，这个性质还是一样的，就是可能重复较多。
这个时候就需要换一个思路，如果先将数组里面的元素打乱，那么按顺序选择前 50 个不就可以了？
是的！
但我们得注意什么叫乱？
一副扑克有 54 张牌，有 54! 种排列方式。所谓的打乱指的是，你所执行的操作，应该能够 等概率地生成 这 54! 种结果中的一种。
所以呢，进入主题了：洗牌算法。
原理很简单：最后一个数和前面任意 n-1 个数中的一个交换，然后倒数第二个数和前面任意 n-2 个数中的一个交换。。。依次下去就行了。
洗牌算法
直接看代码：
public void shuffle(int[] array) {
int length = array.length;
Random random = new Random();
int temp;
while (length > 0) {
int index = random.nextInt(length);
temp = array[index];
array[index] = array[length -1];
array[length -1] = temp;
length--;
}
}
//[1,2,3,4,5,6,7,8,9]
//输出[6 1 7 8 5 2 4 9 3 ]
在整个过程中，这个算法保证了每一个元素出现在每一个位置的概率是相等的。
这个算法真的很牛逼很经典，而且代码很少。
需要更多算法相关，请在公众号回复【算法】，即可获取LeetCode算法刷题精讲
image
****推****荐****阅****读****
**1. **Android进阶资源分享（2月15日更新） ****
2.Android面试题附答案，会了起码30K****
image
image
点“在看”的都涨工资了
image
