探討程序設計語言中排序算法的教學

摘 要：目前排序算法的動態演示多數采用簡單的數字輸出方式，為了清晰而容易地理解程序設計語言中排序算法的思想，更好地掌握排序算法。本文引入立方柱形方式動態演示了排序算法內部交換數據的過程對排序算法的教學進行探討。

關鍵詞：排序；元素；算法

中圖分類號：TP316.2 文獻標識碼：B 文章編號：1002-7661（2013）34-029-02

一、引言

排序就是將線性表中的各元素按關鍵字從小到大（或從大到小）的順序重新排列。在本文里，把作為排序依據的關鍵字稱為排序碼。排序過程一般都涉及到排序碼的比較和元素的移動這兩種基本操作。排序算法的執行時間通常用這兩種基本操作的執行頻度來衡量。在程序設計基礎教學中，排序算法不但是一種基本算法而且還是一種常用的算法，是學生必須掌握的內容。從我多年的程序設計教學中發現往往書中的排序算法的文字描述對學生來說很難理解。程序語言的描述更是不知其所指，這對學生來說很大的打擊了他們學習的積極性，也使得他們很難真正的掌握排序算法，并在實際應用中發揮作用。本文就這一現象問題將排序算法用VC++設計成動態的排序效果生動形象地演示學生看，有助于學生理解并掌握，增強學生學習排序算法的積極性。

本排序動態演示設計的思想是：以一種排序算法作為范例，動態的演示一組數據在這個算法思想下的變化過程，并在動態演示過程中隨時可以調整排序速度以便給學習者有思考的過程，通過動態的演示讓學習者清晰的看到算法的思想。這種動態的演示算法的過程可以推廣到其他排序算法中去，有了這個動態過程的演示，學生就可以輕松的掌握各種算法的思想，并在程序設計的過程中很好的利用。

二、排序算法

常見的排序算法有快速排序、希爾排序、堆排序、選擇排序、起泡排序、折半插入排序、直接插入排序、歸并排序，這些排序算法都各有其優缺點。本文將對起泡排序、選擇排序這兩類進行探討。

1、起泡排序

起泡排序算法的基本思想是：在元素中依次比較兩個相鄰元素的排序碼，若前者比后者大則交換，若前者比后者小則保持不變。先將第一個排序碼與第二個排序碼比較，然后是第二個與第三個比較，直到倒數第二個與最后一個排序碼。比較一輪結束之后，排序碼大的記錄均向后移動。然后開始新一輪的比較，知道一輪比較下來，不再有排序碼的交換發生為止。整個過程就有點像水中的氣泡上升的過程，輕的往上浮，重的向下沉，所以這個算法也叫起泡排序法。算法的步驟如下：

（1）假設要排序的數列為A[1]……A[N]，我們把相鄰的兩個數兩兩進行比較。即把A[1]和A[2]比較，對比完后把A[2]和A[3]進行比較，……直到A[N-1]和A[N]比較完為止。在相鄰的兩個數兩兩進行比較的過程中，如果前面的一個數比后面的一個數大，則把這兩鄰的兩個數交換，也就是說，我們把較小的數放在前面，把較大的數調到后面。即，如果在一次比較中，如果A[1]比A[2]大的情況下，把A[1]和A[2]交換，……以此類推，直到一輪A[N-1]和A[N]比較完。

（2）再次重復（1），直到相鄰兩數之間不再發生交換為止。

2、簡單選擇排序

簡單選擇排序算法的基本思想是：從所有元素中選出排序碼最小的元素，將它與A[0]交換位置；然后，在A[1]～A[N]中選出排序碼最小的元素，將它與A[1]交換位置；依次做下去，在進行了N-1次選擇后排序過程結束。這種排序算法比較的次數與前一種排序算法一樣多，但是交換次數要比起泡排序算法少，效率較高。

三、演示方法

1、傳統方式的演示方法

目前大專院校教師在對語言程序設計中排序算法的內容進行講授時一般采用靜態數字輸出方式，如圖1所示。這種方法對于描述排序算法中交換數據的過程不夠形象生動。

圖1 傳統方式的排序演示方法

2、立方柱形的動態演示方法

（1）設計原理

本排序算法動態演示程序是在VC++6.0集成環境下實現，基于對話框類型的MFC應用程序。為了直觀清楚地表現起泡排序與選擇排序的排序過程，程序設計的主界面如圖2所示。

圖2 排序算法動態演示程序主界面

程序主界面是一個對話框，包含控制區，演示區和說明區三個部分。

控制區位于主界面的上方，主要由下拉組合框控件，按鈕控件，滑動控件以及靜態文本框控件組成。下拉組合框控件供選擇產生多少個隨機數進行動態排序演示，按鈕控件用來控制動態排序演示的開始，滑動控件用來控制演示速度，在需要仔細查看演示過程的時候，可以將滑動塊移到最左邊演示。

演示區位于主界面的中間，由上下兩個繪畫窗口（靜態文本框控件）組成，負責將排序中的數據以立方柱形繪制出來，而不是簡單輸出我們通常熟悉的1、2、3等數字符號，顯得更為直觀，比較有動態演示效果。

說明區位于主界面的右邊，由上下兩個靜態文本框控件組成，是對描述排序算法動態演示的簡單說明。

（2）主要實現過程

首先創建一個基于對話框類型的MFC應用程序SortingDemo，在主對話框上添加所需要的控件。然后，在對話框CSortingDemoDlg的初始化函數OnInitDialog末尾加入控件的初始化代碼。

在CSortingDemoDlg.h中的類SortAlgoWindow里定義m_wndSortAlgo1和m_wndSortAlgo2的2個實例，分別實現對起泡（升序）排序和簡單選擇（升序）排序的動態演示。

類SortAlgoWindow是從CWnd派生的一個窗口類，重載WM_PAINT消息，OnPaint方法里面實現更新后的數組元素的繪制。

類SortAlgoWindow的UpdateSoringData方法會更新并重繪排序中的數據。

void SortAlgoWindow：：OnPaint（）

{ CPaintDC dc（this）； // device context for painting

// TODO： Add your message handler code here

// Do not call CWnd：：OnPaint（） for painting messages

// 繪制面板底色

// 根據排序中的數組元素，繪制立方柱

// 用紅色繪制發生交換的數據1

// 用藍色繪制發生交換的數據2 }

按鈕控件是用來控制排序動態演示的開始，通過創建2個線程實現起泡（升序）排序和簡單選擇（升序）排序的排序過程，并將排序過程以立方柱形顯示到對應的顯示控件中。

void CSortingDemoDlg：：OnBnClickedStart（）

{ AfxBeginThread（BubbleSortProc， this）；

AfxBeginThread（SelectSortProc， this）； }

（3）程序運行

圖3是程序運行時排序過程中的一個截圖，從圖中可以看到，在起泡（升序）排序過程中，相鄰的紅色，藍色2個元素進行了交換，較大的元素向后移動。而在簡單選擇（升序）排序過程中，較小的（藍色）數據被排到了最前面。

圖3 排序算法動態演示程序開始

所有元素按照升序方式排序結束后的最終運行界面如圖4所示。

圖4 排序算法動態演示程序結束

四、結語

我們在進行程序設計中排序算法內容的教學時采用本文中立方柱形方式的動態演示方法講授，由于它的直觀性能夠使得讓抽象的內容不再難以理解，必然能較好地帶動學生學習排序算法的熱情，從而產生良好的效果。

參考文獻：

[1] 譚浩強.語言程序設計（第一版）.華大學出版社，2005.

[2] 薛超英.數據結構（第一版）.中理工大學出版社，2000.

[3] 孫義欣，許 濤，韓淑芹.濰坊教育學院學報，2008.12.