算法1  SELECT
输入：n个元素的数组A[1...n]和整数k，1≤k≤n。
输出：A中的第k小元素。
     1. select(A,1,n,k)
过程   select(A,low,high,k) //注释：A是包含若干元素的数组，其下标范围是[low,high]
     1.   //注释：p是数组A的元素个数
     2. If p<44 then 将A排序 return(A[k])
     3. 令 。将A分成q组，每组5个元素。如果5不整除p，则排除剩余元素。
     4. 将q组中的每一组单独排序，找出中项。所有中项的集合为M。
     5.     //注释：mm为中项集合的中项
     6. 将A[low...high]分成三组
     7. case
         ：retuen select( ,1, ,k)
         ：return mm
         ：return select( ,1, , )
     8. end case
对于以上快速选择算法的伪代码，我们进行简要的分析：首先，如果输入数组A的元素个数小于预定义的阈值44，则算法使用直接的排序方法将元素排序得出第k小元素，至于选择阈值为44的原因将在后面的具体分析中给出。接下来，把n个元素划分成 组，每组由5个元素组成，如果n不是5的倍数，则排除剩余的元素。每组进行排序并取出它的中项即第三个元素。接着将这些中项序列中的中项元素记为mm，它是通过递归计算得到的。算法的步骤6将数组A中的元素划分为三个数组： , , ，其中分别包含小于、等于、大于mm的元素。最后，在第7步，求出第k小的元素出现在三个数组中的哪一个，并根据测试结果，算法或者返回第k小的元素，或者在 或 上递归。 随机化快速选择算法的时间复杂度理论分析与实验研究(4):http://www.751com.cn/jisuanji/lunwen_26425.html