多线程排序算法教学设计——以插入排序为例

张小丹 范兴国 卫泽刚 刘 飞 钱 郁

（宝鸡文理学院物理与光电技术学院，陕西 宝鸡 721016）

0 引言

现代计算机操作系统都是多任务系统[1]，在实际程序软件开发过程中，为了充分利用计算机资源，一般都采用多任务执行程序，因此多线程实现是程序编写中的重要部分[2]。排序是计算机数据处理中的基本操作[3，4]，对排序算法进行多线程实现，可以利用计算机多核处理器资源，显著提高排序效率[5]。很多学生在学习编程语言和排序算法时都是顺序执行的单线程排序任务[6]，对理解多线程编程有一定难度，因此，设计并实现多线程排序可以更好地帮助学生理解多线程实现方式。本文通过化整为零和逐层递进的教学方式，让学生初步理解C++编程语言多线程代码实现方式，并结合经典插入排序算法，完成多线程排序的教学。

1 多线程教学设计

1.1 教学目标

初步理解并掌握多线程创建方法，能够设计并实现一个简单的多线程排序方法。

1.2 教学重难点

对多线程的理解，以及如何设计和实现多线程排序程序。

1.3 教学方法

采用化整为零，逐层递进的教学方法[2]。首先介绍不同的知识点：多线程编程、排序算法，掌握各自的原理和程序实现。其次对多线程排序问题进行分解，分别详细讲解多线程和排序的原理和实现过程。最后将多线程和排序有效结合起来，实现多线程的排序。具体如下：

学生自己先编写带参数的插入排序算法，其中参数用来指定排序的数组和长度，复习归并排序中如何对两组有序数据进行合并，用来合并多线程的排序结果。然后引导学生编写插入排序的多线程（本文以两个线程为例）程序。插入排序的多线程实现具体如下：首先，将待排序数据分成（均分）两个数据块，记录每个数据块的起始位置和长度。其次，多线程调用插入排序函数，对每个数据块进行排序，在排序完成后，对两组有序数组进行合并，具体过程如图1 所示。

图1 多线程排序实现框架示意图

1.4 教学步骤

采用化整为零，逐层深入的方式讲解，首先单线程实现一个输出“Hello”的简单程序，作为多线程的入门例子，然后对其进行多线程调用，观察单线程与多线程调用后的输出结果及执行时间的差别，直观理解两者的区别。

课堂任务一：单线程和多线程输出“Hello”。单线程输出“Hello”参考程序如下：

教学环节一：单线程小结

（1）单线程如何实现五次打招呼？

（2）单线程执行，输出的结果有何特点？

多线程输出“Hello”参考程序如下：

教学环节二：引导

多线程创建过程具体如下，首先引入头文件＜thread〉，其次定义多线程需要调用的函数Greeting，最后创建多线程对象（t1 和t2）并执行。主函数中的join（）函数表示程序执行到这里时，主函数暂停等待，直到线程1（t1）t 和线程2（t2）t 运行结束，主函数再继续运行。

课堂任务二：复习插入排序过程与如何合并两个数组，并编写程序。插入排序方法的参考程序如下：

合并函数，将两个有序数组合并成一个有序数组，参考程序如下：

课堂任务三：编写多线程排序函数，参考程序如下：

教学环节四：小结

使用两个线程对数组排序，首先将待排序数组分成（均分）两个数据块，记录每个数据块的长度与在原来待排序数组中的起始位置，然后创建线程，每个线程均调用排序函数对相应的数据块进行排序。在多线程排序完成后，即每个数据块排序完成后，合并为有序数据，最终实现整个数据的排序。

教学环节五：拓展练习，让学生思考并实现以下两个问题：

（1）能否用上述方式实现4 线程、8 线程的排序过程？对于n（n 为任意整数）线程，如何设计出相应的排序算法？

（2）如果数据分块较多，在合并过程中，能否采用多线程的方式进行合并？

2 结语

对排序算法进行多线程实现，可以充分利用计算机多核处理器资源，显著提高排序效率。本文以排序算法中简单直观的插入排序算法入手，对其进行多线程实现，采用先分后合、循序渐进、拓展练习的思路对插入排序方法的多线程实现进行了详细介绍，由浅入深、环环相扣，降低了学生用C++对插入排序进行多线程实现的难度。最后用两个拓展练习，强化学生对多线程实现的理解，同时提高学生根据问题需求，编写代码解决问题的能力。