ReservoirSample(S[1..n], R[1..k]) for i = 1 to k R[i] := S[i] for i = k+1 to n j := random(1, i) if j <= k R[j] := S[i]
若S为1-10 ， k=3，则R初始为1,2,3
i=4时，1-4随机选取 4则1/4，1-3则3/4.
3, 将4赋值给R[j]->1,2,4
2->1,4,3
1->4,2,3
4->1,2,3
在1-4中随机取3个数即以上四种情况，并且保证了每种情况概率为1/4.
以上为举例，数学证明同理。
i=5时,从5个数中取3，每个数取到概率为3/5，而3个数组合为1/10。循环可能情况恰为（4+6） 次。
证明容易，难以想到。
原文：http://www.cnblogs.com/yumanman/p/7630424.html