张惠艳 陈芳

摘要：基于选择问题的线性时间要求，本文从算法思想、算法实现以及算法复杂度三个部分对《算法设计与分析》课程中“线性时间选择算法”的教学方法进行了探讨，用图形直观地分析了线性时间选择算法的时间复杂度的最好情况和最坏情况，便于学生理解和掌握。

关键词：线性时间选择算法; 二次取中法; 算法复杂度

中图分类号：G642        文献标识码：A

文章编号：1009-3044（2021）35-0260-04

Discussion on the Teaching of Linear Time Selection Algorithm

ZHANG Hui-yan， CHEN Fang

（Huaiyin Normal University， Huaian 223300，China）

Abstract： Based on the linear time requirement of the selection problem， this paper discusses the teaching method of "linear time selection algorithm"in the course of algorithm design and analysis from three parts： algorithm idea， algorithm realization and algorithm complexity. It analyzes the best and worst situation of the time complexity of linear time selection algorithm intuitively with graph， which is convenient for students to understand and master.

Key words： linear time selection algorithm; median of medians rule; algorithm complexity

1引言

《算法设计与分析》是计算机科学与技术专业居于核心地位的专业课程，学生无论是考研究生还是从事IT方面的工作，掌握好这门课的算法理论和算法思想都是非常重要的。这门课不仅要学习基本算法理论，还要用程序设计语言来实现算法，以便学生更好地理解和掌握算法设计的基本方法和技术，有助于学生进一步学习计算机技术，适应更广泛的职业挑战。迄今为止，算法学家们设计了许多基本和经典的算法，如何将这些算法传授给学生，让学生熟练掌握并能运用所学知识解决实际问题，是教授这门学科的教师所面对的主要问题。

大部分高校选用的教材是陈慧楠《算法设计与分析》[1]第二版。教材的算法基本都给出了C++的代码实现，便于学生很好地理解和掌握复杂抽象的算法设计理论。但本课程是一门理论性和实践性都很强的课程，为了取得好的教学效果，很多授课老师都探讨了该课的教学方法[2-8]，提出了自己的教学建议。本文从教学与实践两个环节针对该书的第五章“分治法”中的“线性时间选择算法”谈谈教学体会。

线性时间选择算法是在若干元素中不用排序方法求出其中第k小的方法，并且要求时间复杂度是线性的。文中采用了“二次取中法”并结合递归调用和快速排序的划分思想得到了求第k小的线性时间选择算法。

2 线性时间选择算法的课堂教学

2.1算法描述

1）将S中元素5个一组分成n/5份，每份5个元素，若n不是5的整数倍，剩余元素在分组时不予考虑;

2）每5个一组，分别求出每组中间元素;并通过交换将所有中间值依次存放在序列的最前端;

3）求序列前端M的中间值m*;

4）以二次中间值m*为主元，进行划分操作;

5）如果左子序列元素个数p=k，则k-1为第k小元素;如果左子序列元素个数p>k，则在左子表中继续搜索，如果左子序列元素个数p<k，则在右子表中继续搜索k-p小元素。

首先引导学生如何实现元素分组并将每组元素的中间值调到整个序列的最前端？在不排序的情况下如何求得前端序列的中间值？求得中间值后如何对序列进行划分？划分后如何找到要求的第k小元素？然后结合实例和C++代码来详细讲解这一算法思想。

2.2算法实现

程序主要代码段是select函数：

int select（int k， int left， int right， int r）   //k是第几小数，left为左下标，right为右下标，r为多少个元素一组

{ int n=right-left+1;

if （n <= r）   //问题足够小，返回下标

{ InsertSort（left，right）;

return left+k-1;

}

for （int i=1;i<=n/r; ++i）

{ InsertSort（left + （i - 1）*r，left+i*r-1）;

swap（a[left+i-1]， a[left+（i-1）*r+Ceil（r，2）-1]）;    //將每组元素的中间值集中存放在子表前面

}

int j=select（Ceil（n/r， 2）， left， left+ n/r-1， r）;    //n/r表明一个分了多少组，二次求中间值，其下标为j

swap（a[left]， a[j]）;

j = Partition（left， right）;             //用二次取中值对原序列重新划分

printfMoM（j）;                    //输出二次取中值

if （k == j-left + 1）

return j;

else if （k < j-left + 1）

return select（k， left， j-1， r）;      //左子表第K个元素

else

return select（k-（j-left +1）， j+1， right， r）;   //右子表第k-（j-left+1）小元素

}

select函数中调用InsertSort排序函数，当序列规模不超过5个元素时，可以采用InsertSort排序直接求出第k小元素，并且一次取中值等于二次取中值;如果序列规模超过5个元素，则对序列循环调用InsertSort函数分组排序，并将每一组的中间值调到序列的最前端，可直接调用库函数swap，再递归调用select函数求二次取中值。这里给相应的代码都加上了注释，理解起来更容易;swap函数中还调用了Ceil函数，功能相当于上取整，代码如下：

int Ceil（int x，int y）          //x，y均為整形数

{ if （x%y==0） return x/y;

else return x/y+1;

}

教材中没有给出这个函数，可让学生自己补充上取整函数;紧接着select函数递归调用自身，求得前端序列的中间值，并用这个中间值对整个序列进行划分，即调用Partition函数。最后根据划分的结果以及k值的大小，用if-else语句来选择select函数，继续递归调用，最终得到第k小的值。

2.3算法实例讲解

教材中给了35个元素的求第7小的实例，对这个实例的运行讲解可以很好地让学生理解上述一系列提问。

步骤1：首先将给定的35个元素存入全局数组a：

int a[35]={41，76，55，19，59，63，12，47，67，45，26，76，74，33，18，65，86，49，77，35，80，53，19，97，22，52，62，39，60，59，29，72，31，56，91};并在主函数中通过赋值语句int j=select（7，0，34，5）调用select函数。

步骤2：进入select函数，首先调用InsertSort排序函数，代码如下：

void InsertSort（int left， int right）     //插入排序

{ for （int i=left+1; i<=right;++i）   //从left+1开始进行插入，一直到right结束

{ int temp= a[i];

int j;

for （j=i-1; j>=left&&temp<a[j];j--）

{ a[j+1]=a[j];  }

a[j+1] = temp;

}

}

通过循环7次调用InsertSort排序函数，即依次调用InsertSort（0，4），InsertSort（5，9），InsertSort（10，14），InsertSort（15，19），InsertSort（20，24），InsertSort（25，29），InsertSort（30，34），将7组元素按从小到大的顺序排序，并通过swap函数将每组序列的中间元素依次调至序列的最前端。此时可得到序列的最前端元素依次是55，47，33，65，53，59，56这七个元素。

步骤3：程序执行int j=select（Ceil（n/r，2），left，left+n/r-1，r）这条语句递归调用select函数自身，此处n=35，r=5，Ceil（n/r，2）=Ceil（35/5，2）=4，left=0，left+n/r=7传递给实参right，即运行select（4，0，6，5），即在前端序列的7个元素中找出第4小元素，这是select函数第一次递归调用自身。

步骤4：第二次进入select函数，因7除以5取整结果是1，所以只有第一组元素需要再排序，得结果33，47，53，55，65，通过swap（a[left]，a[j]）语句将53调至序列的最前端得前端序列为53，47，33，55，65，59，56，程序执行int j =Select（Ceil（n/r，2），left，left+n/r-1，r）; 即第三次递归调用select函数，求前端序列53，47，33，55，65的中间值，即执行select（1，0，0，5），直接返回0，完成此次递归调用。

调用printfMoM（j）输出函数，代码如下：

void printfMoM（int j）

{ cout << "二次取中值为：" <<a[j]<<endl;

for （int i=0;i<35;++i）

{ cout << a[i] << " ";

if （（i+1）%5==0）

cout << endl;

}

}

输出结果“二次取中值为53”，这是第一次求得的“二次取中值”。

步骤5：执行j=Partition（left，right）;即调Partition函数，此处left=0，right=7，代码如下：

int Partition（int left， int right）   //划分函数，返回分割点

{

int i = left;    //以最左边的数为分割点

int j = right + 1;  //由于do while先执行--j，为了保证最右边的数参与比较，所以先加一

do

{ do

{ ++i;

} while （a[i] < a[left]）;

do

{ --j;

} while （a[j] > a[left]）;

if （i < j）

swap（a[i]， a[j]）;

} while （i < j）;

swap（a[left]， a[j]）;

return j;

}

即用53對前端7个元素序列进行第一次划分。得到划分结果为33，47，53，55，65，59，56。此时元素53所对应的数组下标为2，即j=2;因为函数select（4，0，6，5）是要求前端序列得第4小元素，此时前端序列只有两个元素，j=2<4，所以第4小元素应是右端序列的第一小元素。

步骤6：执行语句Select（k-（j-left+1），j+1，right，r），即第四次递归调用函数select（1，3，6，5），此时left=3，right=6，n=right-left+1=4，4<5，直接对右端序列55，65，59，56进行插入排序，得55，56，59，65，它的第1小元素即为55，运行结果是返回3，即j=3，因a[3]=55，得到第二次“二次取中值”55。

步骤7：执行swap（a[left]，a[j]）;将55调到序列的最前端，执行j=Partition（left，right）;此处left=0，right=34，即用55完成对原始序列的第一次划分，并printfMoM（j）即输出二次取中值55。

教材对二次取中值55如何得到的讲解得不够细，在得到“二次取中值”55时，程序已经在select（7，0，34，5）函数中递归调用select函数3次，分别是select（4，0，6，5），select（1，0，0，5）得第一次“二次取中值”并对前端序列进行划分，其运行结果如图1;select（1，3，6，5）得第二次“二次取中值”并对原始序列的划分，其运行结果如图2。图中的红色下划线是后标注的，可以清楚地看到“二次取中值”在原序列中的位置。很多同学此处都理解得不够透彻，这里给出了详细的分析运行过程。

步骤8：因为j=17，j-0+1=18>k=7，left=0，故执行语句else if（k<j-left+1） return select（k，left，j-1，r）;即第五次调用函数select（7，0，16，5）。

步骤9：第五次进入select函数，首先调用InsertSort排序函数，此时共17个元素，5个元素一组，只需调用3次InsertSort函数，依次是：InsertSort（0，4），InsertSort（5，9），InsertSort（10，14），将3组元素按从小到大的顺序排序，并通过swap函数将每组序列的中间元素依次调至序列的最前端。此时可得到序列的最前端元素依次是45，31，22，直接插入排序得22，31，45，前端序列共3个元素，求其中间元素，即第2小，递归调用select（2，0，2，5）得到j=1，第6次调用select函数结束，即第三次二次取中值31。用31对原序列的前17个元素进行划分，运行结果如图3所示。可看到划分后31的下标是7，是前17个元素的第8小元素，因此第7小元素应在31的左端继续找。

步骤10：因为j=7，j-0+1=8>k=7，left=0，故执行语句else if（k<j-left+1） return select（k，left，j-1，r）;即调用函数select（7，0，6，5）。

步骤11：第7次进入select函数，执行select（7，0，6，5）此时共7个元素，18，22，26，19，19，12，29。首先调用InsertSort排序函数，5个元素一组，只需1次调用InsertSort函数即InsertSort（0，4），得18，19，19，22，26，取中间值19，第八次调用select（1，0，0，5），得j=0，第八次递归调用结束，得到第四次二次取中值19，并通过swap函数将19调至序列的最前端。用19对这7个元素进行划分，得18，12，19，22，26，19，29，运行结果如图4所示。19的下标j=2，所以j-left+1=2-0+1=3，此时k =7>3，因此第7小元素应在a[2]=19的右侧，执行return select（k-（j-left+1），j+1，right，r），即调用select（4，3，6，5）。

步骤12：第九次进入select函数，此时共4个元素，因此进行InsertSort排序，排序结果是19，22，26，29，调用结束返回select函数，执行return left+k-1，3+4-1=6，即返回下标6，selcet函数调用到此结束，回到主函数，j=6即29即为所求得第7小元素，程序到此运行结束。主函数如下：

int main（）

{

int j=select（7，0，35-1，5）;

cout <<"第七小的值为："<<a[j]<< endl;

return 0;

}

至此教材中选用的35个元素把selcet函数的每一条语句都执行了一次，主函数依次调用了select（7，0，34，5），select（4，0，6，5），select（1，0，0，5），select（1，3，6，5），select（7，0，16，5），select（2，0，2，5），select（7，0，6，5），select（1，0，0，5），select（4，3，6，5），select函数共被调用了9次。教材中此例的元素个数35和各元素的值以及求解第7小的设计都考虑得特别巧妙，这是一个值得所有学算法的学生好好学习的实例，可以很好地帮助学生理解程序的递归调用，提高学生的算法理解和实现能力。

3 线性时间选择算法的复杂度分析

教材中给出了线性时间选择算法的复杂度分析，但不够直观，这里结合图形给出线性时间选择算法的最好和最坏时间复杂度分析。n个元素（元素可重复），5个元素为一组，共分为n/5（最后的几个元素可不考虑）每组按从小到大的顺序排序，如图5所示：

假设m*的左侧有r列，右侧有r列，则问题的规模：n=5（2r+1）=10r+5，子问题最坏情况：3r+2+2r+2r=7r+2;最好情况：3r+2+2r=5r+2，可以根据算法步骤分析得到问题最坏时间复杂度为：T（n）=T（n/5） +T（7/10n）+cn，用递归树易得：T（n）=O（n）;最好时间复杂度为：T（n）=T（n/5）+T（1/2n）+cn，用递归树易得：T（n）=O（n）;因此该算法具有线性时间复杂度。若3个元素一组是否能得到线性时间复杂度？7个元素一组呢？留给读者考虑。

4 结语

线性时间选择算法因为结合了元素的排序、划分以及函数的递归调用，教师在讲解以及学生在理解接受这一算法的过程中都有一定的难度，这里结合本人上课实际情况以及授课效果给出了一种易懂易掌握的方法，该方法收到了非常明显的教学效果，激发了学生对算法学习的兴趣。

参考文献：

[1] 王晓东.算法设计与分析第二版[M].北京：清华大学出版社，2016.

[2] 毕方明，杨文嘉.算法与复杂度分析案例化教学改革[J].教育教学论坛，2018（44）：102-103.

[3] 南姣芬， 杨文雅， 李红婵，等. 《算法设计与分析》教学过程中的思考[J]. 教育现代化， 2019，6（35）：195-196.

[4] 袁李萌子， 周杰. 《算法分析与设计》课程教学初探[J]. 教育现代化， 2019，6（70）：89-90..

[5] 郭惠芳，刘寒冰.算法设计与分析课程研讨教学的探索[J].计算机教育，2018（4）：60-62.

[6] 秦丹.算法设计与分析教学常见问题分析[J].电脑知识与技术，2014，10（24）：5719-5720.

[7] 季晓慧， 姚国清， 张玉清，等. 计算思维与实践编程能力培养并重的算法设计与分析教学[J]. 电脑知识与技术：学术版， 2020，16（4）：70-71.

[8] 范昊，束德勤.《算法設计与分析》课程教学方法研究[J].教育教学论坛，2020（9）：246-247.

【通联编辑：王力】