水库抽样算法是一个典型的空间亚线性算法。
在很多时候我们要在海量数据中进行均匀的抽样，由于我们要取样的是海量数据，以至于只能让这些数据从我们面前流过一次。
水库抽样的要求是，每一时刻取到的样本都是前面已经流过的全部数据的均匀抽样。
例如：连续输入一组未知大小的数据，输出这组数据的k个均匀抽样。要求：输入到前n(n>k)个数据时，保存已经输入的数据的k个均匀抽样。
1.申请长度为k的数组A保存抽样(此处下标用1~k表示)；
2.首先保存接收到的前k个数据；
3.当接收到第i个数据t时，生成[1,i]间的随机数j,若j<=k,则以t替换A[j]。
算法的关键在第三步，每当新来元素t时，生成随机数，一旦随机数落在数组范围之内，就替换掉。
算法原理：
对于每个新到来的元素i，它是以k/i的概率被收入集合的，因为生成的随机数范围是[1,i]，而当数字小于等于k时，才会被替换进数组A。
当第i+1个元素到来时，第i+1个元素被替换进数组的概率是Pi=k/(i+1)，而此时，前一个元素i被从中替换出来的概率为Po=1/k。则当第i+1个元素到来时第i个元素被替换出去的概率为Pi*Po，那么没有被替换出来的概率为p=1-Pi*Po=1-1/(i+1)。
那么当第i+2,i+3...个元素到来时，第i个元素没有被替换出来的概率为1-1/(i+2)，1-1/(1+3)...
那么当元素i被选入集合中，并且在后面的所有的替换中都没有被替换出来的概率：
这样便得到，对于任意一个元素i，其被选入样本的概率均为k/n，也就是说它符合随机抽样。
