余艷，邢遠(yuǎn)秀，劉云冰

（武漢科技大學(xué) 理學(xué)院，湖北 武漢 430065）

幾乎所有的數(shù)據(jù)結(jié)構(gòu)類教材都將“排序”設(shè)為獨(dú)立的一章，其重要性不言而喻.數(shù)據(jù)結(jié)構(gòu)課程在“排序”這一章涵蓋的內(nèi)容通常包括：直接插入排序、希爾排序、冒泡排序、快速排序、簡(jiǎn)單選擇排序、錦標(biāo)賽排序、堆排序、歸并排序和基數(shù)排序[1-2].但在教學(xué)過程中，發(fā)現(xiàn)學(xué)生面對(duì)這一章學(xué)習(xí)內(nèi)容時(shí)卻有些不屑之情：“用Python 的一個(gè)sort()就可以解決的問題，為何要花這么多時(shí)間去學(xué)習(xí)”.作為教師倘若沒有幫助學(xué)生解此疑惑，怕是難以調(diào)動(dòng)起他們的學(xué)習(xí)熱情，更不要提其他更宏偉的教學(xué)目標(biāo)了.當(dāng)學(xué)生心中有所思而不能通時(shí)，正是教師給予教學(xué)的最適宜和最關(guān)鍵時(shí)刻[3].

1 建立學(xué)習(xí)意義感的必要性

哲學(xué)家赫舍爾說，“人之為人的獨(dú)特難題就是如何進(jìn)入意義”[4].當(dāng)學(xué)生在學(xué)習(xí)過程中缺乏學(xué)習(xí)意義感，則會(huì)出現(xiàn)“學(xué)習(xí)奴隸化”現(xiàn)象[5]：對(duì)學(xué)習(xí)內(nèi)容不感興趣，缺乏主動(dòng)思考，學(xué)習(xí)過程淪為被動(dòng)接受教師的安排.這種情況下，無論采取何種教學(xué)方式，呈現(xiàn)何種教學(xué)內(nèi)容，教學(xué)都將只是一個(gè)灌輸符號(hào)的過程[6].

因此，有必要在教學(xué)過程中帶領(lǐng)學(xué)生建立起學(xué)習(xí)的意義感，讓學(xué)生對(duì)學(xué)習(xí)活動(dòng)產(chǎn)生自我認(rèn)同，并在學(xué)習(xí)過程中獲得價(jià)值體驗(yàn).由此激發(fā)學(xué)生的求知欲望和思考能力，產(chǎn)生強(qiáng)烈的學(xué)習(xí)參與意識(shí)，從而實(shí)現(xiàn)真正意義上的教與學(xué).本文以數(shù)據(jù)結(jié)構(gòu)課程中“排序”這一章的教學(xué)為例，以改變學(xué)生初學(xué)“排序”時(shí)所持的學(xué)習(xí)態(tài)度為目標(biāo)，探討引導(dǎo)學(xué)生對(duì)學(xué)習(xí)內(nèi)容產(chǎn)生正確認(rèn)知并建立學(xué)習(xí)意義感的方法.

2 建立學(xué)習(xí)意義感的方法

2.1 分析學(xué)習(xí)現(xiàn)狀，建立學(xué)習(xí)信心

排序算法雖然種類很多，但代碼都不長(zhǎng)，同時(shí)具有一定的難度和實(shí)現(xiàn)細(xì)節(jié)的要求，適合程序設(shè)計(jì)的初學(xué)者進(jìn)階學(xué)習(xí).學(xué)生在數(shù)據(jù)結(jié)構(gòu)正式學(xué)習(xí)之前，通常學(xué)習(xí)了計(jì)算機(jī)基礎(chǔ)和C 語言程序設(shè)計(jì)，所積累的程序設(shè)計(jì)經(jīng)驗(yàn)并不多，依然是程序設(shè)計(jì)的初學(xué)者.排序算法這種“踮踮腳”就可以夠得到的問題，不會(huì)因?yàn)閱栴}的復(fù)雜度而影響學(xué)習(xí)者的信心，同時(shí)排序算法內(nèi)在的細(xì)節(jié)要求也可以打磨學(xué)習(xí)者的思維能力和編程能力，安排在這個(gè)階段進(jìn)行學(xué)習(xí)符合認(rèn)知規(guī)律的要求.

2.2 明確學(xué)習(xí)目標(biāo)的多樣性，產(chǎn)生認(rèn)同感

排序算法的學(xué)習(xí)目標(biāo)并不僅局限于排序算法策略的學(xué)習(xí)，時(shí)間復(fù)雜度、空間復(fù)雜度的分析方法也是數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)過程中需要重點(diǎn)打磨的基本功之一.作為一名專業(yè)的程序開發(fā)者，只有具備了時(shí)間空間復(fù)雜度的觀念、分析方法和權(quán)衡方法，才有能力在工程實(shí)踐中為具體的應(yīng)用問題選擇合適的、正確的算法.

在排序算法的學(xué)習(xí)過程中，學(xué)生將進(jìn)一步學(xué)習(xí)時(shí)間復(fù)雜度、空間復(fù)雜度分析和計(jì)算的方法，并用于比較和評(píng)價(jià)各種排序算法在各種場(chǎng)景下的性能.如果把時(shí)間空間復(fù)雜度的分析看作是編程的一件工具，那么使用這件工具可以幫助學(xué)生理解各種排序算法的特性和適用場(chǎng)合；從另一個(gè)角度來看，“排序”這一章也為學(xué)生提供了學(xué)習(xí)這種工具使用方法的應(yīng)用背景.排序算法時(shí)間復(fù)雜度的對(duì)比分析見表1（其中基數(shù)排序中的d 表示元素的位數(shù)）.

表1 排序算法的對(duì)比分析

2.3 了解崗位需求，激發(fā)學(xué)習(xí)動(dòng)力

真正學(xué)懂計(jì)算機(jī)的人既能用科學(xué)家的嚴(yán)謹(jǐn)思維來求證，也能用工程師的務(wù)實(shí)手段來解決問題.而這種思維和手段的最佳演繹就是“算法”[7].許多大型軟件企業(yè)技術(shù)崗位的面試都很重視對(duì)數(shù)據(jù)結(jié)構(gòu)與算法的考察，且注重能否迅速將解題思路轉(zhuǎn)換為代碼的能力，其中排序算法就是經(jīng)常被考察的問題之一.有程序員在博客中提到自己的面試經(jīng)歷：“很多公司的面試，如百度、騰訊、阿里都問到了堆排序，雖然問的形式不一樣，但都是堆排序的相關(guān)知識(shí)”[8].其他面試經(jīng)歷，例如：“請(qǐng)說出各種排序算法的穩(wěn)定性”[9].“知道哪些排序算法，選一個(gè)自己熟悉的排序算法，講下它的主要特點(diǎn)，如時(shí)間復(fù)雜度、穩(wěn)定性.一般會(huì)把重點(diǎn)放在快速排序和堆排序，進(jìn)一步要求手寫實(shí)現(xiàn).討論下在輸入是特定序列的情況下，當(dāng)前的算法有什么缺點(diǎn)或優(yōu)點(diǎn)”[10].

可見，軟件企業(yè)對(duì)排序算法的考察涉及到對(duì)排序算法策略的理解、代碼實(shí)現(xiàn)、算法穩(wěn)定性的分析以及算法時(shí)間復(fù)雜度的分析等，這些知識(shí)點(diǎn)恰好與數(shù)據(jù)結(jié)構(gòu)的教學(xué)內(nèi)容相吻合.由此可見，要為自己的專業(yè)面試加分，就需要在數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)過程中深入理解各種排序算法的原理和特性，并在實(shí)驗(yàn)環(huán)節(jié)認(rèn)真完成上機(jī)任務(wù)，積累編寫代碼的技巧和經(jīng)驗(yàn).

2.4 審視算法背后的邏輯，實(shí)現(xiàn)正確認(rèn)知

數(shù)據(jù)結(jié)構(gòu)教程中經(jīng)典排序算法種類繁多，在贊嘆每種算法精妙絕倫的思想之余，不能忽視每種排序算法的背后還蘊(yùn)含著不同的知識(shí)點(diǎn)和底層邏輯.通過學(xué)習(xí)不同的算法策略，可以收獲不同角度的思維訓(xùn)練和編程技巧.帶領(lǐng)學(xué)生理解算法背后的邏輯，從而使他們對(duì)排序算法的學(xué)習(xí)擁有更全面的認(rèn)識(shí)，從而獲取學(xué)習(xí)意義感.

2.4.1 學(xué)習(xí)排序算法可以啟迪發(fā)散性思維 “直接插入排序”的想法與手起撲克牌的過程如出一轍.通過不斷地將一張新牌插入到現(xiàn)有的有序序列中，使得有序序列長(zhǎng)度每次增一，最終使得手里起到的所有牌排列有序.這種排序算法的構(gòu)思來源于日常生活，是人類最直觀的一種排序思維.這個(gè)例子也啟發(fā)我們，在求解各類問題時(shí)可以從日常生活甚至是大自然現(xiàn)象中尋求更一般的規(guī)律，從而獲得靈感.在智能計(jì)算領(lǐng)域有很多類似的例子，如粒子群算法，就是通過模擬鳥群覓食行為而發(fā)展起來的一種隨機(jī)搜索優(yōu)化算法.

2.4.2 學(xué)習(xí)排序算法可以收獲普適性的編程思想 遞歸形式的“快速排序”和“歸并排序”都采用了“分而治之”的編程思想.快速排序的“分”對(duì)應(yīng)“一次劃分”的操作，“治”對(duì)應(yīng)樞軸前后2個(gè)子序列分別進(jìn)行快速排序的操作.歸并排序?qū)⒃夹蛄蟹指畛?個(gè)子序列，分別對(duì)2個(gè)子序列進(jìn)行歸并排序，再把2個(gè)有序的子序列歸并成1個(gè)有序的子序列.這2 種排序算法的共性，都是將原始問題分解為規(guī)模更小但性質(zhì)相同的子問題.這種情況下可以用“分而治之”的思想去解決問題，用代碼實(shí)現(xiàn)上述思想就是遞歸程序.可以這么說，“快速排序”和“歸并排序”為“分而治之”提供了應(yīng)用場(chǎng)景；反之，通過對(duì)“快速排序”和“歸并排序”的學(xué)習(xí)，又可以加深對(duì)“分而治之”的理解，更好地掌握遞歸程序編寫的方法和實(shí)現(xiàn)細(xì)節(jié).

2.4.3 學(xué)習(xí)排序算法可以強(qiáng)化對(duì)數(shù)據(jù)結(jié)構(gòu)的理解 “堆排序”利用了“堆”的數(shù)據(jù)結(jié)構(gòu)，它是一種特殊的完全二叉樹.大頂堆上任意結(jié)點(diǎn)上的值都不小于左右孩子結(jié)點(diǎn)的值，小頂堆上任意結(jié)點(diǎn)上的值都不大于左右孩子結(jié)點(diǎn)的值.堆排序的整個(gè)過程就是利用了堆的這種邏輯特性，當(dāng)對(duì)序列按正序排序（元素由小到大），則需要使用大頂堆.創(chuàng)建大頂堆后，最大的元素一定在堆頂，將其與最后一個(gè)元素交換，最大的元素就落到了正確的位置，排序過程可以不再考慮它，稱其為“出堆”.對(duì)于剩余的元素，除了堆頂元素不滿足堆的要求，其左右子樹依然是堆.此時(shí)，從堆頂向下進(jìn)行調(diào)整，稱為“篩選”操作，可以將其重新調(diào)整為一個(gè)“大頂堆”，堆頂元素即為整個(gè)序列的次大元，將其與整個(gè)序列的倒數(shù)第2 個(gè)元素交換，次大元落到正確的位置，次大元即可出堆.這個(gè)過程重復(fù)執(zhí)行，即可實(shí)現(xiàn)整個(gè)序列的排序.

如果沒有“堆排序”的應(yīng)用背景，直接生硬地討論“堆”的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其上的“插入”、“刪除”操作，學(xué)生必然會(huì)覺得枯燥和無味.在“堆排序”的學(xué)習(xí)過程中，才可以深刻體會(huì)到“堆”這種數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)上的巧妙性和存在的必要性，從而加深對(duì)“數(shù)據(jù)結(jié)構(gòu)”這種抽象概念的理解.

2.4.4 學(xué)習(xí)排序算法可以延伸學(xué)習(xí)的深度 借助排序算法的教學(xué)內(nèi)容，可以引導(dǎo)學(xué)生進(jìn)行教材以外的深度思考，如思考算法的改進(jìn)策略并進(jìn)行研究性的實(shí)驗(yàn)探索.如教材中快速排序樞軸元素的選取原則很簡(jiǎn)單：固定選擇第1 個(gè)元素作為樞軸.通過分析快速排序的時(shí)間復(fù)雜度可知，若一次劃分后樞軸兩側(cè)子序列長(zhǎng)度相差很大，即樞軸位置落在最左邊或最右邊，算法的時(shí)間效率就會(huì)退化到O（n2）.為提高算法時(shí)間效率，可考慮使用三者取中（從序列的首元素、中間位置的元素、尾元素中選取中位數(shù)作為樞軸）或五者取中法避免極端情況的發(fā)生，并通過實(shí)驗(yàn)來測(cè)試不同樞軸選取方法對(duì)快速排序算法時(shí)間效率的影響.

除此之外，還可以引導(dǎo)學(xué)生從遞歸的角度思考快速排序的改進(jìn)策略.原始快速排序算法的遞歸操作會(huì)執(zhí)行到序列長(zhǎng)度為1 的情況，通過提前結(jié)束遞歸來提升算法時(shí)間效率：當(dāng)待排子序列長(zhǎng)度小于某個(gè)閾值時(shí)，則終止遞歸調(diào)用，并采用直接插入排序算法.閾值設(shè)定對(duì)算法時(shí)間效率的影響也可以通過實(shí)驗(yàn)來測(cè)試.另外，還可以將這2 種改進(jìn)策略進(jìn)行組合，并通過實(shí)驗(yàn)來測(cè)試改進(jìn)算法在不同排列性質(zhì)的數(shù)據(jù)集上的性能.這些研究性的實(shí)驗(yàn)過程可以由學(xué)生自己來設(shè)計(jì)，實(shí)驗(yàn)的完成可以促進(jìn)學(xué)生獲得學(xué)習(xí)的價(jià)值感.

引導(dǎo)學(xué)生探究工業(yè)界軟件采用的排序算法，也可以增強(qiáng)學(xué)生對(duì)排序算法的學(xué)習(xí)價(jià)值感.如引導(dǎo)學(xué)生調(diào)研Matlab 軟件內(nèi)置排序函數(shù)的實(shí)現(xiàn)方法，會(huì)發(fā)現(xiàn)它是幾種快速算法的智能混合版本，從而體會(huì)到排序算法在工業(yè)實(shí)踐中的真實(shí)應(yīng)用模式.

3 結(jié)語

本文以數(shù)據(jù)結(jié)構(gòu)課程中排序算法的教學(xué)為例，通過建立學(xué)習(xí)信心、產(chǎn)生知識(shí)認(rèn)同感、激發(fā)學(xué)習(xí)動(dòng)力和實(shí)現(xiàn)正確認(rèn)知，幫助學(xué)生建立學(xué)習(xí)意義感.教學(xué)實(shí)踐表明，通過建立學(xué)習(xí)意義感的方法引領(lǐng)教學(xué)過程，可以獲得良好的課堂學(xué)習(xí)氛圍，營(yíng)造積極的師生互動(dòng)情境，授課效果受到了學(xué)生和教學(xué)督導(dǎo)的好評(píng).