随机化快速选择算法的时间复杂度理论分析与实验研究(4)
时间:2018-11-26 11:18 来源:毕业论文 作者:毕业论文 点击:次
算法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小的元素，或者在 或 上递归。 (责任编辑：qin) |