劉建科++馮媛媛

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

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

中圖分類(lèi)號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）17-0117-02

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

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

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

算法思想內(nèi)容過(guò)于抽象，理解困難，不易掌握。學(xué)生一般在看到快速排序的算法思想時(shí)，一時(shí)很難弄明白，也很難理解。單一從文字?jǐn)⑹龇矫鎭?lái)弄懂快速排序算法思想很困難，如果我們換個(gè)思路，先看具體案例，再來(lái)理解算法，就會(huì)發(fā)現(xiàn)該算法思想其實(shí)并不難理解。

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

下面通過(guò)例子來(lái)說(shuō)明快速排序的算法思想：

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

圖1 一趟快速排序

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

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

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

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

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

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

3 方法探討

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

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

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

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

（2）理論聯(lián)系實(shí)際，做好上機(jī)實(shí)驗(yàn)

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

參考文獻(xiàn)：

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

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

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