多線程排序算法教學(xué)設(shè)計
——以插入排序為例

張小丹 范興國 衛(wèi)澤剛 劉 飛 錢 郁

（寶雞文理學(xué)院物理與光電技術(shù)學(xué)院，陜西 寶雞 721016）

0 引言

現(xiàn)代計算機操作系統(tǒng)都是多任務(wù)系統(tǒng)[1]，在實際程序軟件開發(fā)過程中，為了充分利用計算機資源，一般都采用多任務(wù)執(zhí)行程序，因此多線程實現(xiàn)是程序編寫中的重要部分[2]。排序是計算機數(shù)據(jù)處理中的基本操作[3，4]，對排序算法進行多線程實現(xiàn)，可以利用計算機多核處理器資源，顯著提高排序效率[5]。很多學(xué)生在學(xué)習(xí)編程語言和排序算法時都是順序執(zhí)行的單線程排序任務(wù)[6]，對理解多線程編程有一定難度，因此，設(shè)計并實現(xiàn)多線程排序可以更好地幫助學(xué)生理解多線程實現(xiàn)方式。本文通過化整為零和逐層遞進的教學(xué)方式，讓學(xué)生初步理解C++編程語言多線程代碼實現(xiàn)方式，并結(jié)合經(jīng)典插入排序算法，完成多線程排序的教學(xué)。

1 多線程教學(xué)設(shè)計

1.1 教學(xué)目標

初步理解并掌握多線程創(chuàng)建方法，能夠設(shè)計并實現(xiàn)一個簡單的多線程排序方法。

1.2 教學(xué)重難點

對多線程的理解，以及如何設(shè)計和實現(xiàn)多線程排序程序。

1.3 教學(xué)方法

采用化整為零，逐層遞進的教學(xué)方法[2]。首先介紹不同的知識點：多線程編程、排序算法，掌握各自的原理和程序?qū)崿F(xiàn)。其次對多線程排序問題進行分解，分別詳細講解多線程和排序的原理和實現(xiàn)過程。最后將多線程和排序有效結(jié)合起來，實現(xiàn)多線程的排序。具體如下：

學(xué)生自己先編寫帶參數(shù)的插入排序算法，其中參數(shù)用來指定排序的數(shù)組和長度，復(fù)習(xí)歸并排序中如何對兩組有序數(shù)據(jù)進行合并，用來合并多線程的排序結(jié)果。然后引導(dǎo)學(xué)生編寫插入排序的多線程（本文以兩個線程為例）程序。插入排序的多線程實現(xiàn)具體如下：首先，將待排序數(shù)據(jù)分成（均分）兩個數(shù)據(jù)塊，記錄每個數(shù)據(jù)塊的起始位置和長度。其次，多線程調(diào)用插入排序函數(shù)，對每個數(shù)據(jù)塊進行排序，在排序完成后，對兩組有序數(shù)組進行合并，具體過程如圖1 所示。

圖1 多線程排序?qū)崿F(xiàn)框架示意圖

1.4 教學(xué)步驟

采用化整為零，逐層深入的方式講解，首先單線程實現(xiàn)一個輸出“Hello”的簡單程序，作為多線程的入門例子，然后對其進行多線程調(diào)用，觀察單線程與多線程調(diào)用后的輸出結(jié)果及執(zhí)行時間的差別，直觀理解兩者的區(qū)別。

課堂任務(wù)一：單線程和多線程輸出“Hello”。單線程輸出“Hello”參考程序如下：

教學(xué)環(huán)節(jié)一：單線程小結(jié)

（1）單線程如何實現(xiàn)五次打招呼？

（2）單線程執(zhí)行，輸出的結(jié)果有何特點？

多線程輸出“Hello”參考程序如下：

教學(xué)環(huán)節(jié)二：引導(dǎo)

多線程創(chuàng)建過程具體如下，首先引入頭文件＜thread〉，其次定義多線程需要調(diào)用的函數(shù)Greeting，最后創(chuàng)建多線程對象（t1 和t2）并執(zhí)行。主函數(shù)中的join（）函數(shù)表示程序執(zhí)行到這里時，主函數(shù)暫停等待，直到線程1（t1）t 和線程2（t2）t 運行結(jié)束，主函數(shù)再繼續(xù)運行。

課堂任務(wù)二：復(fù)習(xí)插入排序過程與如何合并兩個數(shù)組，并編寫程序。插入排序方法的參考程序如下：

合并函數(shù)，將兩個有序數(shù)組合并成一個有序數(shù)組，參考程序如下：

課堂任務(wù)三：編寫多線程排序函數(shù)，參考程序如下：

教學(xué)環(huán)節(jié)四：小結(jié)

使用兩個線程對數(shù)組排序，首先將待排序數(shù)組分成（均分）兩個數(shù)據(jù)塊，記錄每個數(shù)據(jù)塊的長度與在原來待排序數(shù)組中的起始位置，然后創(chuàng)建線程，每個線程均調(diào)用排序函數(shù)對相應(yīng)的數(shù)據(jù)塊進行排序。在多線程排序完成后，即每個數(shù)據(jù)塊排序完成后，合并為有序數(shù)據(jù)，最終實現(xiàn)整個數(shù)據(jù)的排序。

教學(xué)環(huán)節(jié)五：拓展練習(xí)，讓學(xué)生思考并實現(xiàn)以下兩個問題：

（1）能否用上述方式實現(xiàn)4 線程、8 線程的排序過程？對于n（n 為任意整數(shù)）線程，如何設(shè)計出相應(yīng)的排序算法？

（2）如果數(shù)據(jù)分塊較多，在合并過程中，能否采用多線程的方式進行合并？

2 結(jié)語

對排序算法進行多線程實現(xiàn)，可以充分利用計算機多核處理器資源，顯著提高排序效率。本文以排序算法中簡單直觀的插入排序算法入手，對其進行多線程實現(xiàn)，采用先分后合、循序漸進、拓展練習(xí)的思路對插入排序方法的多線程實現(xiàn)進行了詳細介紹，由淺入深、環(huán)環(huán)相扣，降低了學(xué)生用C++對插入排序進行多線程實現(xiàn)的難度。最后用兩個拓展練習(xí)，強化學(xué)生對多線程實現(xiàn)的理解，同時提高學(xué)生根據(jù)問題需求，編寫代碼解決問題的能力。