多线程排序实例

多线程排序实例 (1)在 Delphi 7 中新建一个工程。 将窗体的 Caption 属性设置为“利用多线程比较排序速度”，Name 属性设置 SortForm;在窗体上添加 3 个 Label 组件，将它们的 Caption 属性分别设置为“冒泡排序”、“选择排序”和“快速排序”;再在窗体中添加一个 Button 组件，并将其 Caption 属性设置为“开始排序”，Name 属性设置为 StarBtn;再添加 3 个 PaintBox 组件，Name属性分别为:bubblesortbox，selectionsortbox，QuickSortBox，用于显示排序线段;最后向窗体添加 3 个 Bevel 组件，用于表示 3 组排序线段的显示区域，并将它们的位置和大小分别设置成和 3 个 PaintBox 组件的相同。如图: (2)下面进行程序代码的编写。 在排序之前要有 3 个数据:BubbleSortArray、SelectonSortArray 和 QuickSortArray，它们分别作为参数传送给 3 个线程。而在程序初始化时需要对它们进行赋值，因此，在程序中添加对主窗体 Form1的 OnCreate 事件的处理函数，在其中进行初始化。初始化时，生成一个由随机数组成的数组，用它来初始化 个待排序的数组。为了随时显示排序的中间结果，需要在程序运行的过程中及时地根据排序的中间结果显示相应的线段排列。因此，还需要分别添加 3 个 PaintBox 组件的 OnPanint 事件处理函数，在其中根据数据的当前值，重新显示相应的线段排列。 最后需要线程的生成和线程结束的处理函数。线程的生成在 StarBtn 的 OnClick 事件的处理函数中完成。在生成线程的时候分别将 3 个数组传递给 3 个线程，之后将 StarBtn 的 Enabled 姿态设置为 False，以使得在排序过程中按钮是不可用的。在线程结束的处理函数中再将 StarBtn 的 Enabled 设置为 True，以使按钮可以再次使用。 其中窗体单元文件 Unit1 中的代码如下: unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, ExtCtrls, StdCtrls; type Tsortform = class(TForm) Label1: TLabel; Label2: TLabel; Label3: TLabel; starbtn: TButton; bubblesortbox: TPaintBox; selectionsortbox: TPaintBox; QuickSortBox: TPaintBox; Bevel1: TBevel; Bevel2: TBevel; Bevel3: TBevel; procedure BubbleSortBoxPaint(Sender: TObject); procedure SelectionSortBoxPaint(Sender: TObject); procedure QuickSortBoxPaint(Sender: TObject); procedure starbtnClick(Sender: TObject); procedure FormCreate(Sender: TObject); private { Private declarations } ThreadsRunning: Integer; procedure RandomizeArrays; procedure ThreadDone(Sender: TObject); public { Public declarations } procedure PaintArray(Box: TPaintBox; const A: array of Integer); end; var sortform: Tsortform; implementation {$R *.dfm} uses unit2; type PSortArray = ^TSortArray; TSortArray = array[0..114] of Integer; var ArraysRandom: Boolean; BubbleSortArray, SelectionSortArray, QuickSortArray: TSortArray; procedure Tsortform.PaintArray(Box: TPaintBox; const A: array of Integer); //根据数组值，在 PaintBox 组件上绘制线段 var I: Integer; begin with Box do begin Canvas.Pen.Color := clRed; for I := Low(A) to High(A) do PaintLine(Canvas, I, A[I]); //在位置 I 绘制一条长度为 A[I]的线段 end; end; procedure Tsortform.BubbleSortBoxPaint(Sender: TObject); begin PaintArray(BubbleSortBox, BubbleSortArray); end; procedure Tsortform.SelectionSortBoxPaint(Sender: TObject); begin PaintArray(SelectionSortBox, SelectionSortArray); end; procedure Tsortform.QuickSortBoxPaint(Sender: TObject); begin PaintArray(QuickSortBox, QuickSortArray); end; procedure Tsortform.starbtnClick(Sender: TObject); begin RandomizeArrays; //生成随机数组 ThreadsRunning := 3; //创建 3 个排序线程线程 with TBubbleSort.Create(BubbleSortBox, BubbleSortArray) do OnTerminate := ThreadDone; with TSelectionSort.Create(SelectionSortBox, SelectionSortArray) do OnTerminate := ThreadDone; with TQuickSort.Create(QuickSortBox, QuickSortArray) do OnTerminate := ThreadDone; StarBtn.Enabled := False; end; procedure Tsortform.FormCreate(Sender: TObject); begin RandomizeArrays; end; procedure TSortForm.RandomizeArrays; var I: Integer; begin if not ArraysRandom then begin Randomize; for I := Low(BubbleSortArray) to High(BubbleSortArray) do BubbleSortArray[I] := Random(170); //生成随机数 SelectionSortArray := BubbleSortArray; QuickSortArray := BubbleSortArray; ArraysRandom := True; Repaint; end; end; procedure TSortForm.ThreadDone(Sender: TObject); //线程结束处理函数 begin Dec(ThreadsRunning); if ThreadsRunning = 0 then //判断 3 个线程是否都已经结束 begin StarBtn.Enabled := True; ArraysRandom := False; end; end; end. 下面进行线程部分的实现。由于 3 个线程有着很多相同之处，而仅仅只是具体的排序方法存在着区别，因此程序中从 TThread 类中派生出 TSortThread 类，在其中实现线程的大部分功能，并定义一个抽象函数 Sort。然后再从 TSortThread 类中分别派生出 TbubbleSort、TselectionSort 和 TquickSort 3个派生类，它们只需要重载 Sort 函数，实现具体的排序功能即可。 在 TSortThread 类中需要一个 Create 构造函数，在其中进行一些必要的初始化工作，如获取排序数组的一些信息，设置线程的 FreeOnTerminate 属性等。另外还需要一个重绘排序线段的函数，用于在排序时每次进行交换操作后重新绘制交换后的线段排列。因为涉及到对 VCL 的操作，所以使用了Synchronize 方法使线程同步。 线程实现单元 Unit2 的完整代码如下: unit Unit2; interface uses Classes, Graphics, ExtCtrls; type { TSortThread } PSortArray = ^TSortArray; TSortArray = array[0..MaxInt div SizeOf(Integer) - 1] of Integer; TSortThread = class(TThread) //排序线程 private FBox: TPaintBox; FSortArray: PSortArray; FSize: Integer; FA, FB, FI, FJ: Integer; procedure DoVisualSwap; protected procedure Execute; override; procedure VisualSwap(A, B, I, J: Integer); procedure Sort(var A: array of Integer); virtual; abstract; //执行排序的抽象函数 public constructor Create(Box: TPaintBox; var SortArray: array of Integer); end; { TBubbleSort } TBubbleSort = class(TSortThread) //冒泡排序线程 protected procedure Sort(var A: array of Integer); override; end; { TSelectionSort } TSelectionSort = class(TSortThread) //选择排序线程 protected procedure Sort(var A: array of Integer); override; end; { TQuickSort } TQuickSort = class(TSortThread) //快速排序线程 protected procedure Sort(var A: array of Integer); override; end; procedure PaintLine(Canvas: TCanvas; I, Len: Integer); implementation procedure PaintLine(Canvas: TCanvas; I, Len: Integer); //绘制线段，I 标志线段的位置，Len 标志线段的长度 begin Canvas.PolyLine([Point(0, I * 2 + 1), Point(Len, I * 2 + 1)]); end; { TSortThread } constructor TSortThread.Create(Box: TPaintBox; var SortArray: array of Integer); //线程的构造函数，执行初始化工作 begin FBox := Box; FSortArray := @SortArray; FSize := High(SortArray) - Low(SortArray) + 1; FreeOnTerminate := True; inherited Create(False); end; procedure TSortThread.DoVisualSwap; //覆盖交换前的线段 begin with FBox do begin Canvas.Pen.Color := clBtnFace; PaintLine(Canvas, FI, FA); PaintLine(Canvas, FJ, FB); //重新绘制交换后的线段 Canvas.Pen.Color := clRed; PaintLine(Canvas, FI, FB); PaintLine(Canvas, FJ, FA); end; end; procedure TSortThread.VisualSwap(A, B, I, J: Integer); //重绘制交换后的线段 begin FA := A; FB := B; FI := I; FJ := J; Synchronize(DoVisualSwap); //通过 Synchronize 完成对 VCL 的访问 end; procedure TSortThread.Execute; begin Sort(Slice(FSortArray^, FSize)); //执行排序 end; { TBubbleSort } procedure TBubbleSort.Sort(var A: array of Integer); //选择排序 var I, J, T: Integer; begin for I := High(A) downto Low(A) do for J := Low(A) to High(A) - 1 do if A[J] > A[J + 1] then begin VisualSwap(A[J], A[J + 1], J, J + 1); //重新绘制交换后的线段 T := A[J]; A[J] := A[J + 1]; A[J + 1] := T; if Terminated then Exit; end; end; { TSelectionSort } procedure TSelectionSort.Sort(var A: array of Integer); //选择排序 var I, J, T: Integer; begin for I := Low(A) to High(A) - 1 do for J := High(A) downto I + 1 do if A[I] > A[J] then begin VisualSwap(A[I], A[J], I, J); //重新绘制交换后的线段 T := A[I]; A[I] := A[J]; A[J] := T; if Terminated then Exit; end; end; { TQuickSort } procedure TQuickSort.Sort(var A: array of Integer); //快速排序 procedure QuickSort(var A: array of Integer; iLo, iHi: Integer); var Lo, Hi, Mid, T: Integer; begin Lo := iLo; Hi := iHi; Mid := A[(Lo + Hi) div 2]; repeat while A[Lo] < Mid do Inc(Lo); while A[Hi] > Mid do Dec(Hi); if Lo <= Hi then begin VisualSwap(A[Lo], A[Hi], Lo, Hi); //重新绘制交换后的线段 T := A[Lo]; A[Lo] := A[Hi]; A[Hi] := T; Inc(Lo); Dec(Hi); end; until Lo > Hi; if Hi > iLo then QuickSort(A, iLo, Hi); if Lo < iHi then QuickSort(A, Lo, iHi); if Terminated then Exit; end; begin QuickSort(A, Low(A), High(A)); end; end.