基于.NET多線程的幾種排序算法的圖形化實現

郭忠南

（無錫機電高等職業技術學校，江蘇 無錫 214028）

0 引言

當一個程序開始運行時，它就是一個進程。線程是進程中的一個執行流，每個線程都有自己的專有寄存器（棧指針、程序計數器等），但代碼區是共享的，即不同的線程可以執行同樣的函數。多線程是指程序中包含多個執行流，即在一個程序中可以同時運行多個不同的線程來執行不同的任務。在本質和結構上來說，.NET是一個多線程的環境，多線程編程技術在.NET中具有相當重要的地位。

1 排序算法

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

1.1 冒泡排序法

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

1.2 快速排序法

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

1.3 選擇排序法

選擇排序法的基本思想是每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最后，直到全部待排序的數據元素排完。

2 程序實現

2.1 三種排序算法效率對比

在算法學習過程中，我們常常會通過編寫代碼來驗證算法的效率。為此，我們可以在Visual Studio中編寫控制臺程序，隨機生成一組數據，然后分別用三種排序算法進行排序，記錄各種算法的排序時間。獲取排序時間的核心代碼如下：

程序對10萬個數據進行測試，三種排序時間如圖1所示，執行效率可見一斑。

圖1 十萬個數據三種排序時間

2.2 多線程實現排序圖形化

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

2.2.1 窗體項目

新建窗體項目布局如圖2所示，三個Panel控件用于繪圖。

圖2 界面控件布局圖

2.2.2 編寫自定義類CSort.cs

其中實現冒泡排序、選擇排序和快速排序，以及在Panel控件上繪圖。排序算法實現代碼此處不再贅述，需要說明的是，在排序算法中，每次交換數據，需要調用一次如下DrawData函數以實現圖形的動態顯示：

2.2.3 編寫主窗體代碼

（1）初始化數組，核心代碼如下InitializeData方法實現。

（2）聲明三個排序算法對應的線程，并編寫三個線程將要使用的方法。

冒泡排序法線程對應的線程方法代碼如下，其他排序法對應的方法雷同，不再贅述。

2.2.4 運行程序

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

圖3 排序過程效果圖

2.3 思考拓展

通過多次產生10000個數據并模擬，我們可以看到，選擇排序法最先完成，其次是快速排序法，最慢的是冒泡排序法，這似乎與快速排序法速度最快相矛盾。經過分析，我們可以發現，快速排序之所以比選擇排序看起來要慢，是因為在快速排序算法中理論的交換數據的次數要多于快速排序，而每交換一次數據，就要用圖形顯示出來。快速排序看起來慢完全是因為繪圖次數多造成的。由此，我們可以在排序結束后給出排序時間，并繪出排序后的效果。由此，修改線程theBubbleSort－Thread的線程方法BubbleSortProc如下：

運行程序，生成10萬個數據，程序運行過程和運行結果如圖4和圖5所示。

圖4 十萬個數據排序中

圖5 十萬個數據排序后

從圖中可以看到，快速排序用時31.25毫秒，選擇排序用時23234.375毫秒，冒泡排序用時51906.25毫秒。這樣的運行結果與圖1控制臺下面的排序效率對比出來的數據比較吻合。

另外，在實際教學中，會遇到查看排序過程的情形。由此我們不妨對程序中畫線的速度加以控制。如圖6所示，加入一個trackBar控件來調整速度，線條右側顯示該數據值，具體代碼不再一一列舉。

圖6 可以控制排序節奏的排序實例運行中

3 結束語

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

［1］嚴蔚敏，吳偉民.數據結構（第二版）［M］.北京：清華大學出版社，2001.

［2］張千帆.數據結構與算法：C語言實現［M］.北京：科學出版社，2009.

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