选择问题（selection problem）是求一个n个数列表的第k个最小元素的问题。这个数字被称为第k个顺序统计量（order statistic）。当然，对于k=1或者k=n的情况，我们可以扫描整个列表，找出最小或者最大的元素。对于其他情况，我们可以对列表进行排序，然后返回第k个元素。

可是，对于整个列表进行排序是不是小题大做？因为该问题仅仅是要找出第k小的元素，而不是要求把列表从小到大排列。

我们可以将给定的列表根据某个值p（例如列表的第一个元素）进行划分。一般来说，这是对列表元素的重新整理，使左边部分包含所有小于等于p的元素，紧接着是中轴（pivot）p本身，再接着是所有大于等于p的元素。如下图所示

有两种主要的划分方法，本文讨论 Lomuto 划分，以后会介绍更有名的 Hoare 划分。

Lomuto（洛穆托）划分的伪代码如下：

[3]. 如果s