基于.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.