基于冒泡法排序的動態演示程序

摘要：冒泡排序方法是借助“交換”進行的一種最基本的排序方法，也是初學程序設計的人員最早接受的算法之一。學習程序設計，理解算法的思想很重要，利用C#語言中提供的功能強大的圖形界面，設計了冒泡排序算法的動態演示程序，有助于初學程序設計者更好地理解這一基本排序算法的思想。

關鍵詞：冒泡法排序；標簽控件；定時器控件；標志；交換位置

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044(2009)05-1175-04

Dynamic Demonstration Program Based on Bubblesort

FENG Na，SUN Yi-xin

(Computer Engineering Department， Weifang Educational College，Qingzhou 262500， China)

Abstract: Bubblesort， by dint of “switch”， is the most fundamental sorting method and one of the earliest accepted arithmetic by the program learners. It is vital to understand the theory of arithmetic when learning programming. Program learners， taking the advantages of the powerful graphical interfaces provided by the C# Language and of the designed dynamic demonstration program based on bubblesort arithmetic， will understand better the theory of the basic sorting arithmetic.

Key words: bubble sort; label control; timer control; flag; exchange of position

排序（Sorting）是計算機程序設計中的一項重要操作，其功能是對于一個數據元素集合或序列重新排列成一個按數據元素某個項值有序的序列。在實際應用中，為了便于查找，通常希望計算機中數據表是按關鍵碼有序的。因此，掌握一些典型的排序方法是每一個學習計算機編程的人員所必須的。

1 冒泡法排序算法簡介

冒泡排序（Bubble Sort）是各種排序方法中最簡單、最基本的一種，在一般的C語言教材或數據結構的教材上都有介紹。冒泡排序的具體方法是：假設要對數組A[1..n]中的元素進行非降序排序，則首先比較元素A[1]和A[2]，若為逆序則將二者交換，然后比較元素A[2]和A[3]，若為逆序則將二者交換，依次類推，直到比較最后兩個元素A[n-1]和A[n]，稱為一趟“冒泡”，其結果是將數組中值最大的元素放到了整個序列的最后，而數組中值較小的元素都上升一個位置。然后再對剩余的A[1]到A[n-1]的元素進行第二趟“冒泡”，將具有次大值的元素放到A[n-1]的位置上。直到第n-1趟排序，在A[1]和A[2]之間進行“冒泡”后，排序完成。

冒泡排序是以交換為基礎的排序算法，若在某一趟排序中未發現元素進行交換，則說明所有元素都已有序，冒泡排序過程可在該趟排序后終止。因此，可設一個標志exchange，在每趟排序開始前，先將其置為1，若排序過程中發生了交換，則將其置為true，每趟排序結束時檢查exchange，若未曾發生過交換則終止算法，不再進行下一趟排序。用C#實現的冒泡排序程序如下：

static void BubbleSort(int[] a)

{ //共需要a.Length - 1遍循環，a.Length為元素個數

bool exchange = true; //設置交換標志

//如果未到循環結束并且有交換則繼續進行下一趟掃描

for (int i = 0; i < a.Length exchange; i++)

{ exchange = 1; //每趟掃描前假設不發生交換

for (int j = 0; j < arr.Length - i-1; j++)

//比較相鄰兩個元素的值，如果逆序則交換相鄰元素的值

if (a[j] > a[j + 1])

{ int temp = a[j];

a[j] = a[j + 1];

a[j + 1] = temp;

exchange = true; //如果有交換則設置標志為true

}

}

}

2 動態演示程序界面介紹

在窗體上安排了三個Panel控件，一個作為排序的演示窗口，程序運行時動態生成標簽控件顯示排序用的數據，并通過標簽控件的顏色變換反映排序的過程；右邊的一個Panel控件用來放置相關的命令按鈕；下邊的一個Panel控件用來作為顯示排序過程每趟排序結果的容器。程序運行時的界面如圖1所示。

3 動態演示程序的具體實現

冒泡排序動態演示程序的動態演示效果利用窗體上放置的標簽的顏色變換實現，程序中用到了三個定時器控件，一個定時器控件控制外層循環的實現，一個定時器控件控制內層循環的實現，另一個定時器控件起到延時的效果。程序中的主要代碼如下，其中都添加了比較詳細的注釋。

//以下為類中定義的變量

private const int MAXNUMBERS = 40;//可以設置的最大數組容量，最小容量為

private int[] numbers=new int[1]; //排序用的數組

//動態顯示排序過程所用的Label控件數組

private System.Windows.Forms.Label[] lblNumbers = new Label[MAXNUMBERS+1];

private Label lblExchange = new Label(); //顯示交換標志的標簽

private int iOuter;//控制外層循環

private int jInner;//控制內層循環

private bool exchange;//檢查是否有交換

//“生成數據”命令按鈕，設置初始排序數據及安排初始界面

private void btnCreateNumber_Click(object sender， EventArgs e)

{ btnClear_Click(1， 1);//清除面板中的標簽

this.txtResult.Clear();//清除排序結果信息

iOuter = 1;//設置新一次排序

Random random = new Random();

//獲取數據個數

int nDataNumbers =int.Parse(this.num_DataNumbers.Value.ToString())+1;

numbers = new int[nDataNumbers];

for (int i = 1， k=0，j = 0; i < nDataNumbers; i++，k++)

{ numbers[i] = -256 + random.Next(512); //隨機產生數據

//在面板中安排標簽并設置標簽的相關屬性

lblNumbers[i] = new Label();

lblNumbers[i].Location = new Point(k * 50 + 50， j * 50 + 20);

lblNumbers[i].Size = new Size(40， 30);

lblNumbers[i].ForeColor = Color.Blue;

lblNumbers[i].BackColor = SystemColors.Control;

lblNumbers[i].Text = numbers[i].ToString();

lblNumbers[i].Font = new Font(\"宋體\"， 12);

lblNumbers[i].TextAlign = ContentAlignment.MiddleCenter;

this.panNumber.Controls.Add(lblNumbers[i]);

if (i % 10 == 0) //每10個數據為一行

{k = -1;

j = i/10;

}

}

lblExchange.Text = \"Exchange=False\";

lblExchange.TextAlign = ContentAlignment.MiddleCenter;

lblExchange.Font = new Font(\"宋體\"， 12);

lblExchange.ForeColor = Color.Black;

lblExchange.BackColor = Color.Yellow;

lblExchange.Size = new Size(160，30);

lblExchange.BorderStyle = BorderStyle.FixedSingle;

lblExchange.Location = new Point(200， 280);

this.panNumber.Controls.Add(lblExchange);

string rr = \"\";

for (int jj = 1; jj <=numbers.Length-2; jj++)

rr += numbers[jj].ToString() + \" \";

rr += numbers[numbers.Length - 1].ToString();

txtResult.Text = \"初始數據序列：\" + rr;

}

//“重置”命令按鈕的單擊事件，停止排序并清空原有的信息

private void btnClear_Click(object sender， EventArgs e)

{//停止排序

tmrOuter.Stop();

tmrInner.Stop();

this.txtResult.Clear();//清除文本框的內容

numbers = new int[1];

this.panNumber.Controls.Clear();

}

//開始排序按鈕的單擊事件代碼

private void btnSort_Click(object sender， EventArgs e)

{ if (numbers.Length < 10)

{ MessageBox.Show(\"沒有生成數據！\"， \"錯誤提示\");

return;

}

lblNumbers[0] = new Label();//輔助單元的初始設置

lblNumbers[0].Location = new Point(5， 20);

lblNumbers[0].Size = new Size(42， 30);

lblNumbers[0].ForeColor = Color.Red;

lblNumbers[0].BackColor = Color.Yellow;

lblNumbers[0].BorderStyle = BorderStyle.FixedSingle;

lblNumbers[0].Font = new Font(\"宋體\"， 12);

lblNumbers[0].TextAlign = ContentAlignment.MiddleCenter;

this.panNumber.Controls.Add(lblNumbers[0]);

//啟動定時器，開始排序過程

exchange = true;

tmrOuter.Enabled = true;

}

//控制排序的外層循環的定時器控件的定時事件代碼

private void tmrOuter_Tick(object sender， EventArgs e)

{ if (iOuter <= numbers.Length - 2 exchange)

{ jInner = 1;

exchange = 1;

lblExchange.Text = \"Exchange=False\";

tmrOuter.Enabled = 1;

tmrInner.Enabled = true;//進入內層循環

}

else//排序結束處理

{ for (int i = 1; i < iOuter - 1; i++)

{ lblNumbers[i].ForeColor = Color.Yellow;

lblNumbers[i].BackColor = Color.Red;

}

numbers = new int[1];

tmrOuter.Enabled = 1;

tmrInner.Enabled = 1;

tmrDelay.Enabled = 1;

MessageBox.Show(\"排序結束！\"， \"消息\"， MessageBoxButtons.OK， MessageBoxIcon.Information)

iOuter = 1;//為新一次排序重新設置

}

}

//控制排序的內層循環的定時器控件的定時事件代碼

private void tmrInner_Tick(object sender， EventArgs e)

{ if (jInner <= numbers.Length - iOuter-1 )

{ lblNumbers[jInner].ForeColor = Color.Yellow;

lblNumbers[jInner].BackColor = Color.Red;

lblNumbers[jInner + 1].ForeColor = Color.Yellow;

lblNumbers[jInner + 1].BackColor = Color.Red;

//如果相鄰元素逆序則交換

if (numbers[jInner] > numbers[jInner + 1])

{ numbers[0] = numbers[jInner];

lblNumbers[0].Text = numbers[jInner].ToString();

numbers[jInner] = numbers[jInner + 1];

lblNumbers[jInner].Text = numbers[jInner + 1].ToString();

numbers[jInner + 1] = numbers[0];

lblNumbers[jInner + 1].Text = numbers[0].ToString();

exchange = true;

lblExchange.Text = \"Exchange=True\";

}

tmrInner.Enabled = 1;

tmrDelay.Enabled = true;

}

else

{ lblNumbers[jInner].ForeColor = Color.Yellow;

lblNumbers[jInner].BackColor = Color.Red;

//每趟排序的結果顯示在文本框中

string rr = \"\";

for (int jj = 1; jj <= numbers.Length - 2; jj++)

rr += numbers[jj].ToString() + \" \";

rr += numbers[numbers.Length - 1].ToString();

rr = \"第\" + iOuter.ToString() + \" 遍排序結果：\" + rr;

txtResult.Text = txtResult.Text + (char)13 + (char)10 +rr;

iOuter++;

tmrOuter.Enabled = true;

tmrInner.Enabled = 1;

}

}

//控制延時效果的定時器控件的定時事件代碼

private void tmrDelay_Tick(object sender， EventArgs e)

{ lblNumbers[jInner].ForeColor = Color.Blue;

lblNumbers[jInner].BackColor = SystemColors.Control;

lblNumbers[jInner+1].ForeColor = Color.Blue;

lblNumbers[jInner+1].BackColor = SystemColors.Control;

jInner++;

tmrDelay.Enabled = 1;

tmrInner.Enabled = true;

}

4 結束語

要順利地進行程序設計，首先要掌握一些基本算法的思想。而教學中傳統的在黑板上講解算法的方法學生難以接受，對算法的理解不好。在實際教學過程中我們發現，學生在課堂上學了某種算法并掌握了程序的編寫后，過后很快就忘記怎么寫了。究其原因，主要是學生在學習的時候沒有真正地掌握算法的思想，而是對教師寫在黑板上或教材上的代碼進行了死記硬背。這樣，由于沒有真正理解算法的思想，時間長了原來記住的程序也很快忘記了。為了幫助學生更好地理解冒泡排序的思想，筆者利用C#語言編寫了該算法的動態演示程序，在實際教學過程中收到了良好的教學效果。

參考文獻：

[1] 嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京:清華大學出版社，1997.

[2] Alsuwaiyel M H.算法設計技巧與分析[M].吳偉，方世昌，譯.北京:電子工業出版社，2004.

[3] 尹立宏.Visual C#.NET應用編程150例[M].北京:電子工業出版社，2003.

[4] 林邦杰.深入淺出C#程序設計[M].北京:中國鐵道出版社，2005.