- 上一篇：企业IP地址优化与管理+文献综述
- 下一篇：JPcap网络流量监控的设计与实现
算法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小的元素，或者在 或 上递归。