水塘抽样是一系列的随机算法，其目的在于从包含n个项目的集合S中选取k个样本，其中n为一很大或未知的数量，尤其适用于不能把所有n个项目都存放到主内存的情况。最常见例子为Jeffrey Vitter在其论文[1]中所提及的算法R。

参照Dictionary of Algorithms and Data Structures[2]所载的O(n)算法，包含以下步骤（假设阵列S以0开始标示）：

從S中抽取首k項放入「水塘」中對於每一個S[j]項（j ≥ k）：   隨機產生一個範圍從0到j的整數r   若 r < k 則把水塘中的第r項換成S[j]項

水塘抽样是一系列的随机算法，其目的在于从包含n个项目的集合S中选取k个样本，其中n为一很大或未知的数量，尤其适用于不能把所有n个项目都存放到主内存的情况。最常见例子为Jeffrey Vitter在其论文[1]中所提及的算法R。

参照Dictionary of Algorithms and Data Structures[2]所载的O(n)算法，包含以下步骤（假设阵列S以0开始标示）：

從S中抽取首k項放入「水塘」中對於每一個S[j]項（j ≥ k）：   隨機產生一個範圍從0到j的整數r   若 r < k 則把水塘中的第r項換成S[j]項