劉建科++馮媛媛

摘要：快速排序算法是基于關(guān)鍵字比較的一種內(nèi)排序，其算法思想抽象，文章分析了教學(xué)中存在的問題，提出了先講典型案例，再去理解算法思想的教學(xué)方法，從而促進學(xué)生對抽象算法思想的理解和掌握，提高了課堂教學(xué)效率。

關(guān)鍵詞：快速排序；教學(xué)要點

中圖分類號：TP301.6 文獻標(biāo)識碼：A 文章編號：1009-3044（2016）17-0117-02

排序是將一個數(shù)據(jù)元素（或記錄）的任意系列重新排成一個按關(guān)鍵字有序序列。快速排序作為內(nèi)排序的一種，在所有同數(shù)量級（Ologn）排序方法中，其平均性能（時間復(fù)雜度、空間復(fù)雜度）優(yōu)于其它內(nèi)排序方法。

快速排序的算法思想：通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬蓚€部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，然后分別對這兩個部分記錄繼續(xù)進行排序，直到整個序列有序。

1 快速排序算法在教學(xué)中存在的問題

算法思想內(nèi)容過于抽象，理解困難，不易掌握。學(xué)生一般在看到快速排序的算法思想時，一時很難弄明白，也很難理解。單一從文字?jǐn)⑹龇矫鎭砼焖倥判蛩惴ㄋ枷牒芾щy，如果我們換個思路，先看具體案例，再來理解算法，就會發(fā)現(xiàn)該算法思想其實并不難理解。

在待排序的n個記錄中任取一個記錄（通常取第一個記錄）作為樞軸，把該記錄放入最終位置后，數(shù)據(jù)序列被此記錄分割成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的記錄放置在前一部分，所有比它大的記錄放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一趟快速排序。

下面通過例子來說明快速排序的算法思想：

例：設(shè)記錄關(guān)鍵字集合key={49，38，66，90，75，10，20}。請寫出快速排序第一趟之后的狀態(tài)。

圖1 一趟快速排序

一趟排序之后的狀態(tài)：{20 38 10 49 75 90 66}。

我們可以把一次交換分成兩個步驟：一是從右向左查找第一個小于關(guān)鍵字的記錄，找到并交換位置；二是從左向右查找第一個大于關(guān)鍵字的記錄，找到并交換位置；完成一趟快速排序，一般情況下需要多次交換，直到滿足排序結(jié)束的條件：“在一趟排序過程中沒有進行過交換記錄的操作”。

一趟快速排序后記錄關(guān)鍵字集合被劃分為兩個部分，然后分別對這兩部分進行快速排序：

2 快速排序算法的不足之處

快速排序算法有兩點不足，一是若初始記錄序列按關(guān)鍵字有序或基本有序時，速度反而最慢；二是排序結(jié)果不穩(wěn)定。

在所有同數(shù)量級O（nlogn））的排序方法中，快速排序被認(rèn)為平均性能最好，但是，若初始記錄序列按關(guān)鍵字有序或基本有序時，快速排序?qū)⑼懟鹋菖判颍鋾r間復(fù)雜度O（n2）。

3 方法探討

由于數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容繁多、理論抽象、邏輯性強、難以理解等特點，造成教師教學(xué)費力，學(xué)生學(xué)習(xí)吃力，教學(xué)效果不理想，教師在教學(xué)內(nèi)容的選擇方面，存在“重理論，輕實踐”的普遍現(xiàn)象。目前部分教師仍采用傳統(tǒng)教學(xué)方法——“滿堂灌”（講授法），忽略了學(xué)生的主體地位，在講授理論的同時，不觀察學(xué)生的聽課反映，未給學(xué)生留出思考時間，缺少與學(xué)生的互動環(huán)節(jié)，這樣可能學(xué)生跟不上老師的思路， 降低了聽課效率。

針對教學(xué)中存在的問題，提出如下建議：

（1）采取案例教學(xué)，激發(fā)學(xué)習(xí)興趣

案例教學(xué)法具有較強溝通性、針對性、實踐性等特點。課堂教學(xué)中運用案例教學(xué)法，將理論知識融入案例之中，運用案例引導(dǎo)學(xué)生主動學(xué)習(xí)，激發(fā)學(xué)習(xí)興趣。案例教學(xué)法的核心——案例必須是優(yōu)選的。好的案例對于學(xué)生掌握基本概念、基本知識，培養(yǎng)基本技能起到積極的推動作用。

（2）理論聯(lián)系實際，做好上機實驗

學(xué)習(xí)算法，不僅要理解教材上的理論知識，更重要的是能夠聯(lián)系實際，能針對實際問題編寫出正確易讀、結(jié)構(gòu)清晰、執(zhí)行效率高的程序，上機實驗也是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)必不可少的教學(xué)環(huán)節(jié)，對于訓(xùn)練學(xué)生編程能力，加深抽象理論的理解至關(guān)重要。

參考文獻：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].

[2] 葉振，李小波.地方性院校數(shù)據(jù)結(jié)構(gòu)課程教學(xué)探索[J].電腦知識與技術(shù)，2015（26）.

[3] 陳燕，屈莉莉，李桃迎.數(shù)據(jù)結(jié)構(gòu)課程難點講授方法與必備知識[J].教育教學(xué)論壇，2015（27）.