维基百科指出，快速选择算法（Link）的平均运行时间为O（n）。但是，我不清楚这是怎么回事。谁能（通过递归关系+主方法使用）向我解释平均运行时间如何为O（n）？
因为
我们已经知道我们所需元素位于哪个分区。
我们不需要对所有元素进行排序（通过对它们进行分区），而只需要对所需的分区进行操作。
与快速排序一样，我们必须先将一半分割成，然后再将一半分割成一半，但是这次，我们只需要在期望元素的两个 单一* 分割（一半）中进行下一轮分割躺在。
就像（不是很准确）
n + 1/2 n + 1/4 n + 1/8 n + ..... <2 n
所以它是O（n）。
为了方便起见，使用了一半，但实际分区并不精确为50％。
