快速排序算法的教學要點與方法探討

劉建科++馮媛媛

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

關鍵詞：快速排序；教學要點

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

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

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

1 快速排序算法在教學中存在的問題

算法思想內(nèi)容過于抽象，理解困難，不易掌握。學生一般在看到快速排序的算法思想時，一時很難弄明白，也很難理解。單一從文字敘述方面來弄懂快速排序算法思想很困難，如果我們換個思路，先看具體案例，再來理解算法，就會發(fā)現(xiàn)該算法思想其實并不難理解。

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

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

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

圖1 一趟快速排序

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

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

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

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

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

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

3 方法探討

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

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

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

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

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

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

參考文獻：

[1] 嚴蔚敏，吳偉民.數(shù)據(jù)結構（C語言版）[M].

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

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