基于.NET多線程的幾種排序算法的圖形化實(shí)現(xiàn)

郭忠南

（無錫機(jī)電高等職業(yè)技術(shù)學(xué)校，江蘇 無錫 214028）

0 引言

當(dāng)一個(gè)程序開始運(yùn)行時(shí)，它就是一個(gè)進(jìn)程。線程是進(jìn)程中的一個(gè)執(zhí)行流，每個(gè)線程都有自己的專有寄存器（棧指針、程序計(jì)數(shù)器等），但代碼區(qū)是共享的，即不同的線程可以執(zhí)行同樣的函數(shù)。多線程是指程序中包含多個(gè)執(zhí)行流，即在一個(gè)程序中可以同時(shí)運(yùn)行多個(gè)不同的線程來執(zhí)行不同的任務(wù)。在本質(zhì)和結(jié)構(gòu)上來說，.NET是一個(gè)多線程的環(huán)境，多線程編程技術(shù)在.NET中具有相當(dāng)重要的地位。

1 排序算法

三種最基本的排序方法是冒泡法、選擇法和快速排序法，它們的平均時(shí)間復(fù)雜度分別是：O（n2）、O（n2）和 O（nlogn），其中 n 為待排序元素的數(shù)目。關(guān)于時(shí)間復(fù)雜度，此處只給出一種形象的解釋：O（n）可理解為 n 的常數(shù)倍，則 O（n2）為 n2 的常數(shù)倍，O（nlogn）為nlogn的常數(shù)倍。由于nlogn比n2小得多，所以快速排序的速度顯然優(yōu)于其它兩者。冒泡排序與選擇排序的平均時(shí)間復(fù)雜度是一樣的，似乎二者的速度應(yīng)該接近，但是冒泡排序算法中數(shù)據(jù)移動(dòng)的次數(shù)多于選擇排序，導(dǎo)致選擇排序比冒泡排序速度要快。為了闡述方便，設(shè)定待排序的數(shù)據(jù)均為整數(shù)，排序的結(jié)果是從小到大排列。

1.1 冒泡排序法

冒泡法的原理很簡(jiǎn)單，基本思想就是比較相鄰的兩個(gè)數(shù)據(jù)，若前者比后者大則交換，若前者比后者小則保持不變。也就是將第一個(gè)數(shù)據(jù)與第二個(gè)數(shù)據(jù)比較，然后是第二個(gè)與第三個(gè)，直到倒數(shù)第二個(gè)與最后一個(gè)數(shù)據(jù)比較。這是第一趟冒泡排序，其結(jié)果是使得最大的數(shù)據(jù)被安置到最后一個(gè)位置上。然后進(jìn)行第二趟冒泡排序，對(duì)前面的n-1個(gè)數(shù)據(jù)進(jìn)行同樣的操作，其結(jié)果是使次大的數(shù)據(jù)被安置到第n-1個(gè)數(shù)據(jù)的位置上。

1.2 快速排序法

快速排序法基本思想是通過一趟排序，將待排序的數(shù)據(jù)分為獨(dú)立的兩部分，其中一部分?jǐn)?shù)據(jù)均比另一部分?jǐn)?shù)據(jù)大。然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序。假設(shè)要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過程稱為一趟快速排序。

1.3 選擇排序法

選擇排序法的基本思想是每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。

2 程序?qū)崿F(xiàn)

2.1 三種排序算法效率對(duì)比

在算法學(xué)習(xí)過程中，我們常常會(huì)通過編寫代碼來驗(yàn)證算法的效率。為此，我們可以在Visual Studio中編寫控制臺(tái)程序，隨機(jī)生成一組數(shù)據(jù)，然后分別用三種排序算法進(jìn)行排序，記錄各種算法的排序時(shí)間。獲取排序時(shí)間的核心代碼如下：

程序?qū)?0萬個(gè)數(shù)據(jù)進(jìn)行測(cè)試，三種排序時(shí)間如圖1所示，執(zhí)行效率可見一斑。

圖1 十萬個(gè)數(shù)據(jù)三種排序時(shí)間

2.2 多線程實(shí)現(xiàn)排序圖形化

為了能更加形象地顯示各種排序情況，我們可以在.NET中采用多線程與GDI+技術(shù)。多線程技術(shù)確保三種排序算法獨(dú)立運(yùn)行；GDI+技術(shù)用來實(shí)現(xiàn)排序的圖形化顯示。實(shí)現(xiàn)的主要步驟如下：

2.2.1 窗體項(xiàng)目

新建窗體項(xiàng)目布局如圖2所示，三個(gè)Panel控件用于繪圖。

圖2 界面控件布局圖

2.2.2 編寫自定義類CSort.cs

其中實(shí)現(xiàn)冒泡排序、選擇排序和快速排序，以及在Panel控件上繪圖。排序算法實(shí)現(xiàn)代碼此處不再贅述，需要說明的是，在排序算法中，每次交換數(shù)據(jù)，需要調(diào)用一次如下DrawData函數(shù)以實(shí)現(xiàn)圖形的動(dòng)態(tài)顯示：

2.2.3 編寫主窗體代碼

（1）初始化數(shù)組，核心代碼如下InitializeData方法實(shí)現(xiàn)。

（2）聲明三個(gè)排序算法對(duì)應(yīng)的線程，并編寫三個(gè)線程將要使用的方法。

冒泡排序法線程對(duì)應(yīng)的線程方法代碼如下，其他排序法對(duì)應(yīng)的方法雷同，不再贅述。

2.2.4 運(yùn)行程序

在文本框中輸入10000，點(diǎn)“重新生成數(shù)據(jù)”按鈕，然后點(diǎn)“開始模擬排序”按鈕，如圖3所示。

圖3 排序過程效果圖

2.3 思考拓展

通過多次產(chǎn)生10000個(gè)數(shù)據(jù)并模擬，我們可以看到，選擇排序法最先完成，其次是快速排序法，最慢的是冒泡排序法，這似乎與快速排序法速度最快相矛盾。經(jīng)過分析，我們可以發(fā)現(xiàn)，快速排序之所以比選擇排序看起來要慢，是因?yàn)樵诳焖倥判蛩惴ㄖ欣碚摰慕粨Q數(shù)據(jù)的次數(shù)要多于快速排序，而每交換一次數(shù)據(jù)，就要用圖形顯示出來?？焖倥判蚩雌饋砺耆且?yàn)槔L圖次數(shù)多造成的。由此，我們可以在排序結(jié)束后給出排序時(shí)間，并繪出排序后的效果。由此，修改線程theBubbleSort－Thread的線程方法BubbleSortProc如下：

運(yùn)行程序，生成10萬個(gè)數(shù)據(jù)，程序運(yùn)行過程和運(yùn)行結(jié)果如圖4和圖5所示。

圖4 十萬個(gè)數(shù)據(jù)排序中

圖5 十萬個(gè)數(shù)據(jù)排序后

從圖中可以看到，快速排序用時(shí)31.25毫秒，選擇排序用時(shí)23234.375毫秒，冒泡排序用時(shí)51906.25毫秒。這樣的運(yùn)行結(jié)果與圖1控制臺(tái)下面的排序效率對(duì)比出來的數(shù)據(jù)比較吻合。

另外，在實(shí)際教學(xué)中，會(huì)遇到查看排序過程的情形。由此我們不妨對(duì)程序中畫線的速度加以控制。如圖6所示，加入一個(gè)trackBar控件來調(diào)整速度，線條右側(cè)顯示該數(shù)據(jù)值，具體代碼不再一一列舉。

圖6 可以控制排序節(jié)奏的排序?qū)嵗\(yùn)行中

3 結(jié)束語

排序算法、多線程程序設(shè)計(jì)以及GDI+技術(shù)是程序員必將面臨的重點(diǎn)和難點(diǎn)，文章通過實(shí)例分析了多線程排序圖形化的一些主要步驟和技巧。普通的多線程排序圖形動(dòng)態(tài)顯示不能用于模擬排序算法的效率，因?yàn)榕判蜻^程中的動(dòng)態(tài)畫線非常浪費(fèi)時(shí)間，不能如實(shí)反映算法的效率。如果想對(duì)比排序效率，可以采用先排序后繪圖，并且直觀地給出排序耗時(shí)的方式。如果只想查看排序過程，不進(jìn)行效率對(duì)比，可以采用在排序算法中每交換一次數(shù)據(jù)即繪圖，并引入速度控制的方式。

［1］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（第二版）［M］.北京：清華大學(xué)出版社，2001.

［2］張千帆.數(shù)據(jù)結(jié)構(gòu)與算法：C語言實(shí)現(xiàn)［M］.北京：科學(xué)出版社，2009.

［3］杰瑞夫（Jeffrey，J.），克里斯托夫（Christophe，N.）.Windows核心編程技術(shù)（第5版）［M］.北京：清華大學(xué)出版社，2008.