陈晓梅　胡春花

摘要：针对线性时间选择问题，分别对一般情况下的算法思路和最坏情况下的算法思路进行介绍，结合教学过程和特点，通过增加递归调用的结束条件、无需改造划分函数而直接调用以及对相同划分元素进行集中排列等，对算法进行了优化和改进，增强了算法的连贯性和适用性，使学生更加直观深刻地理解和应用线性时间选择问题的算法，收到较好的教学效果。

关键词：线性时间选择；最坏情况；基准元素；划分

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）21-0087-02

1 线性时间选择问题描述

给定 n 个元素的集合，集合中的第 k 个顺序统计量是指集合中的第k 个（1≤k≤n） 最小元素。当k=1时，指集合中的最小元素；当k=n时，指集合中的最大元素。如何从给定的集合中找出第 k 个最小元素，被称为元素选择问题。线性时间选择问题是指在线性时间内实现元素选择。该问题在大规模数据检索和人工智能搜索方面有广泛的应用。同时该问题也是分治算法教学中的一个典型例子。

2 实现线性时间选择的典型分治算法

2.1 一般性选择问题的分治算法

对于一般的选择问题，可使用RandomizedSelect（a，p，r，k）实现在期望情况下对数组a[p：r]在线性时间内选出第k小的元素。教材中的函数描述如下：

RandomizedSelect（）函数中引入随机划分函数RandomizedPartition（p，r）对数组a[p：r]进行划分，该函数以a[p：r]中的一个随机元素作为划分基准，将原数组划分为两个子数组a[p：i]和a[i+1：r]，使得第一个子数组中的所有元素全小于等于第二个子数组中的所有元素。……