數(shù)據(jù)結(jié)構(gòu)排序算法學(xué)習(xí)意義感的建立

余艷，邢遠秀，劉云冰

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

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

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

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

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

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

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

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

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

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

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

表1 排序算法的對比分析

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)語

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