《數(shù)組應用排序》設計

《數(shù)組應用-排序》教學設計（1）教學目標：知識與技能：1、理解用一維數(shù)組解決數(shù)據(jù)排序的原理；2、掌握使用交換排序法對數(shù)組排序的編程方法。過程與方法：1、通過演示交換排序的步驟，學生掌握程序設計中排序的過程；2、通過分析交換排序中的數(shù)據(jù)的交換和比較，學生掌握排序問題的解決轉換成算法和程序表示的方法。情感態(tài)度價值觀：通過分析交換排序中對數(shù)據(jù)一輪輪的比較，學生養(yǎng)成仔細、耐心的習慣。教學重點難點：交換排序算法的要點和算法設計教學過程：一、設置任務有一項體育運動項目，它的評分要求如下：有若干個裁判；每個裁判對運動員的完成情況打分；在計算最終得分前，必須將所有裁判的分值從小到大排好。請學生設計一個程序，在獲取了每個裁判打的分值后，能夠自動地將這些分數(shù)從小到大排好。二、活動步驟1、問題分析這里的所有數(shù)據(jù)為各個裁判對運動員完成情況的打分。例如現(xiàn)在有8個裁判的打分，將這8個正數(shù)存放在數(shù)組a中：A9．0下標01234567將它們從小到大排序后數(shù)組a中的數(shù)據(jù)如下：A下標01234567排序后滿足：a(0)≤a(1)≤a(2)≤a(3)≤a(4)≤a(5)≤a(6)≤a(7)。讓學生先自學一段有關排序的介紹，同時思考：什么是排序？把雜亂無章的數(shù)據(jù)變?yōu)橛行虻臄?shù)據(jù)，這一過程稱為排序（sorting）。交換排序用了幾重循環(huán)，每重循環(huán)的作用是什么？需要二重循環(huán)：有多少個數(shù)需要確定排序位置是外循環(huán)；確定第i個數(shù)的排序位置需和它后面的數(shù)逐個比較，是內循環(huán)；(3)交換排序中數(shù)據(jù)比較的特點是什么？第i重循環(huán)是將第i個數(shù)和第i+1個數(shù)…第n個數(shù)逐一進行比較,以確定第i小的數(shù).（4）在交換排序中數(shù)據(jù)比較和數(shù)據(jù)交換有什么聯(lián)系？通過數(shù)據(jù)比較確定是否進行數(shù)據(jù)交換。教師演示第0輪過程提問：第1輪循環(huán)和第0輪比有什么特點？學生練習：請學生寫出第2輪結束后a數(shù)組中的元素。2、確定算法流程圖交換排序過程的關鍵：從小到大排序的話，是一個雙重循環(huán)，有多少個數(shù)需要確定排序位置是外循環(huán)，第i次內循環(huán)是找到一個第i小的數(shù)放入i位置。學生思考：如有M個數(shù)（1）為什么只要做M-1輪操作就夠了？（2）交換排序比較兩個元素大小的次數(shù)是多少次？M*(M-1)/2（3）在最不理想情況下，對M個元素排序需要做幾次交換操作？M*(M-1)/2（4）如果要從大到小排序，判斷應怎么寫？a(i)<a(j)3、編寫程序同學可以參照下面殘缺的程序，根據(jù)注釋，補全下劃線處的空缺語句n＝7Fori=0Ton-1'第i輪Forj=i+1Ton'第j個數(shù)和第i個數(shù)比較Ifa(i)>a(j)Then'交換條件t=a(i)a(i)=a(j)a(j)=tEndIfNextjNexti4、檢驗程序的正確性（1）老師介紹和演示測試程序?！吧伞卑粹o自動產生10個隨機數(shù)存放在a數(shù)組中，從a(0)-a(9)?！芭判颉卑粹o激活“單步演示”和“自動演示”按鈕，以開始這兩個操作?！皺z查”按鈕看結果是否已從小到大排序了?！半S機測試”是自動產生數(shù)據(jù)序列并測試。（2）請同學打開c:\sort文件夾中的程序，將上面的排序程序加入到class1中的csort過程中。說明：每次數(shù)據(jù)交換后必須調用swap()過程以將數(shù)據(jù)傳遞到測試程序，將Callswap(a,i,j,s,ns)寫在三句數(shù)據(jù)交換的語句后面即可。三、教學小結和拓展：1、教師對本堂課進行小結，交換排序的關鍵：定義數(shù)組a（n），數(shù)據(jù)輸入到a（1）-a（n）中，外循環(huán)變量i從1ton-1，內循環(huán)變量j從i+1ton,發(fā)現(xiàn)a（i）>a（j）則交換。2、在排序中，影響算法性能的主要部分是循環(huán)和交換，顯然，循環(huán)和交換次數(shù)越多，性能就越差。交換排序怎么樣可以減少交換次數(shù)？請學生研究學習一些其它的排序方法。交換排序方法某些問題的處理過程依賴于數(shù)據(jù)的有序性。把雜亂無章的數(shù)據(jù)變?yōu)橛行虻臄?shù)據(jù)，這一過程稱為排序（sorting）。排序是計算機程序經常使用的基本算法，也是現(xiàn)實生活經常要用到的一種數(shù)據(jù)處理方法。在排序的過程中，比較和交換是兩種基本的操作。交換法是一種典型的排序方法。它的基本思想是按照升序要求（或降序要求）依次確定a(0)、a(1)、……a(n)。在確定第i小的數(shù)a（i）是什么時，可先比較a(i)與a(i+1)，若a(i+1)小（或大），就將a(i)和a(i+1)的內容互換；然后a(i)再與a(i+2)比較，若a(i+2)小（或大），仍要互換a(i)和a(i+2)的內容；……就這樣，將第i小（或大）的值一直換到a(i)處。接下來，再按照上述方法確定a(i+1)、a(i+2)……。每一輪，都是把未排序部分的最?。ɑ虼螅┰負Q到已排序部分的相鄰處。經過n-1輪操作，整個數(shù)組即按升序（或降序）排列好。除了交換排序外，還有選擇排序、冒泡排序、快速排序、合并排序、計數(shù)排序和桶排序等等。每一種算法都有自己的特點，所以要根據(jù)實際情況選擇排序算法?！緦W生練習】1、第1輪結束時a中數(shù)據(jù)776543210下標a寫出第2輪結束時a中數(shù)據(jù)776543210下標a2、根據(jù)流程圖填寫完整程序n＝7'為了程序的通用性，用n表示數(shù)據(jù)個數(shù)Fori=0To_______'第i輪Forj=________Ton'第j個數(shù)和第i個數(shù)比較If________Then'交換條件t=a(i)a(i)=a(j)a(j)=tEndIfNextjNext