數據結構排序算法學習意義感的建立

余艷，邢遠秀，劉云冰

（武漢科技大學 理學院，湖北 武漢 430065）

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

1 建立學習意義感的必要性

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

因此，有必要在教學過程中帶領學生建立起學習的意義感，讓學生對學習活動產生自我認同，并在學習過程中獲得價值體驗.由此激發學生的求知欲望和思考能力，產生強烈的學習參與意識，從而實現真正意義上的教與學.本文以數據結構課程中“排序”這一章的教學為例，以改變學生初學“排序”時所持的學習態度為目標，探討引導學生對學習內容產生正確認知并建立學習意義感的方法.

2 建立學習意義感的方法

2.1 分析學習現狀，建立學習信心

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

2.2 明確學習目標的多樣性，產生認同感

排序算法的學習目標并不僅局限于排序算法策略的學習，時間復雜度、空間復雜度的分析方法也是數據結構學習過程中需要重點打磨的基本功之一.作為一名專業的程序開發者，只有具備了時間空間復雜度的觀念、分析方法和權衡方法，才有能力在工程實踐中為具體的應用問題選擇合適的、正確的算法.

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

表1 排序算法的對比分析

2.3 了解崗位需求，激發學習動力

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

可見，軟件企業對排序算法的考察涉及到對排序算法策略的理解、代碼實現、算法穩定性的分析以及算法時間復雜度的分析等，這些知識點恰好與數據結構的教學內容相吻合.由此可見，要為自己的專業面試加分，就需要在數據結構學習過程中深入理解各種排序算法的原理和特性，并在實驗環節認真完成上機任務，積累編寫代碼的技巧和經驗.

2.4 審視算法背后的邏輯，實現正確認知

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

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

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

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

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

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

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

引導學生探究工業界軟件采用的排序算法，也可以增強學生對排序算法的學習價值感.如引導學生調研Matlab 軟件內置排序函數的實現方法，會發現它是幾種快速算法的智能混合版本，從而體會到排序算法在工業實踐中的真實應用模式.

3 結語

本文以數據結構課程中排序算法的教學為例，通過建立學習信心、產生知識認同感、激發學習動力和實現正確認知，幫助學生建立學習意義感.教學實踐表明，通過建立學習意義感的方法引領教學過程，可以獲得良好的課堂學習氛圍，營造積極的師生互動情境，授課效果受到了學生和教學督導的好評.