運城職業(yè)技術(shù)大學(xué)教案(本科）20—20學(xué)年第學(xué)期課程名稱數(shù)據(jù)結(jié)構(gòu)課程性質(zhì)學(xué)時授課班級授課教師教案首頁教學(xué)單元名稱第十章內(nèi)部排序第2節(jié)排序算法教學(xué)內(nèi)容1.排序的定義2.插入排序和選擇排序課時2授課地點教室授課所需教具、工具、軟件、耗材等多媒體、黑板、粉筆教學(xué)目標(biāo)知識目標(biāo)能力目標(biāo)素質(zhì)目標(biāo)通過學(xué)習(xí)不同的排序方法，體會不同的排序思維對排序效率的影響，形成自己對排序的理解，開拓思維，注重創(chuàng)新教學(xué)重難點重點難點教學(xué)方法與手段講授、演示、討論、案例分析、實驗課程資源備注教案一、導(dǎo)入新課（5分鐘）通常希望計算機中的表是按關(guān)鍵字有序的。因為有序的順序表可以采用查找效率較高的折半查找法，其平均查找長度為log2(n+1)-1,而無序的順序表只能進行順序查找，其平均查找長度為(n+1)/2。因此，本次課我們學(xué)習(xí)排序算法。二、講授新課（75分鐘）1.排序的定義（10分鐘）假設(shè)含n個記錄的序列為：{R1,R2,…,Rn}其對應(yīng)的關(guān)鍵字序列為：{K1,K2,…,Kn}需確定1,2,…,n的一種排列p1,p2,…,pn，使其相應(yīng)的關(guān)鍵字滿足如下的非遞減（或非遞增）關(guān)系：Kp1≤Kp2≤…≤Kpn使其成為一個按關(guān)鍵字有序的序列：{Rp1,Rp2,…,Rpn}假設(shè)Ki=Kj（1≤i≤n，1≤j≤n，i≠j），且在排序前的序列中Ri領(lǐng)先于Rj（即i<j）。若在排序后的序列中Ri領(lǐng)先于Rj則稱所用的排序方法是穩(wěn)定的；反之，若可能使排序后的序列中Rj領(lǐng)先于Ri,則稱所用的排序方法是不穩(wěn)定的。2.直接插入排序（10分鐘）直接插入排序是一種最簡單的排序方法，它的基本操作是將一個記錄插入到巳排好序的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。例如，已知待排序的一組記錄的初始排列如下所示：R(49)，R(38)，R(65)，R(97)，R(76)，R(13)，R(27)，R(49)3.希爾排序（20分鐘）希爾排序又稱縮小增量排序，也屬于插入類排序，但時間效率上有了很大改進。它的基本思想是：先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。例如：注意：這三趟排序的增量分別是5、3、1。4.冒泡排序（15分鐘）冒泡排序是一種借助“交換”進行排序的辦法，每一趟排序都使得最大的關(guān)鍵字被放到最后的位置。例題如下5.快速排序（20分鐘）快速排序是對冒泡排序的一種改進。它的基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。例題如下：三、課堂小結(jié)（5分鐘）本次課我們了解了排序的基本概念，把一個無序的序列進行排序可以有效提高查找的效率，進而提高計算機運算速度。我們通過對四種排序方法的學(xué)習(xí)，基本掌握了排序的過程和思維，在解決實際問題時，又多了一種有