C語言項目開發(fā)基礎(chǔ)與實戰(zhàn)-教案 第39講 快速排序

第頁學(xué)院教師課時授課教案 編號：39授課日期授課班級授課學(xué)時2課型理實課題：快速排序教學(xué)目標(biāo)：本講將向?qū)W生簡要介紹快速排序的的相關(guān)基礎(chǔ)知識，具體目標(biāo)包括：1．掌握快速排序的概念及相關(guān)術(shù)語的含義；2.掌握快速排序的數(shù)據(jù)存儲結(jié)構(gòu)；3．掌握快速排序算法的實現(xiàn)方法。重點與難點：快速排序的概念及相關(guān)術(shù)語的含義，快速排序的數(shù)據(jù)存儲結(jié)構(gòu)，快速排序算法的實現(xiàn)方法。解決措施：使用多媒體教學(xué)工具，在電子課件的幫助下，結(jié)合提問、討論及互動等多種教學(xué)方法，再輔以綜合示例予以解決。教學(xué)方法設(shè)計：講授，討論，演示教學(xué)資源：PPT，DEV-C編譯器，多媒體教學(xué)工具

學(xué)院教案用紙第39講教學(xué)環(huán)節(jié)教學(xué)內(nèi)容教學(xué)組織與教學(xué)方法組織教學(xué)引入新課重點難點難點難點總結(jié)1．考勤；2．對上講課及作業(yè)批改情況進行總結(jié)；3．介紹本講課內(nèi)容及相關(guān)重難點。直接插入排序的時間復(fù)雜度只有O(n2)，雖然后期其他的插入排序算法有所改進，但時間復(fù)雜度基本相同，仍然不夠高→最快，最高效的排序算法：快速排序，時間復(fù)雜度：O(nlogn)。補充：快速排序一、冒泡排序算法1.原理（略）2.示意二、快速排序(QuickSort)算法1.算法原理快速排序是對起泡排序的一種改進，它的基本思想是，通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。2.樞軸(pivot)的概念與作用假設(shè)待排序的序列為{L.r[s],L.r[s+1],…,L.r[t]}，首先任意選取一個記錄（通?？蛇x第一個記錄L.r[s]）作為樞軸（或支點），然后按原則重新排列其余記錄：將所有關(guān)鍵字較它小的記錄都安置在它的位置之前，較它大的都安置在其之后。3.一趟排序的做法附設(shè)兩個指針low和high，它們的初值分別為low和high，設(shè)樞軸記錄的關(guān)鍵字為pivotkey，則首先從high所指位置起向前搜索找到第一個關(guān)鍵字小于pivotkey的記錄和樞軸記錄互相交換，然后從low所指位置起向后搜索，找到第一個關(guān)鍵字大于pivotkey的記錄和樞軸記錄互相交換，重復(fù)這兩步直到low=high為止。4.示例5.參考程序⑴主程序voidmain(){ printf("BeforeSorting:\t\t"); printData(); intmid; mid=quickSort(low,high); printf("AfterQuickSorting:\t"); printData(); insSorting(low,mid-1); insSorting(mid+1,high); printf("AfterSorting:\t\t"); printData();}⑵一次快速排序intquickSort(intlow,inthigh){ intkey=data[low]; boolsign=false; while(low<high){ if(!sign){ if(key<=data[high]){ high--; } else{ data[low]=data[high]; data[high]=key; low++; sign=true; } } else{ if(key>=data[low]){ low++; } else{ data[high]=data[low]; data[low]=key; high--; sign=false; } } } data[low]=key; //ordata[high]=key; returnlow;}⑶插入排序冒泡排序算法的數(shù)據(jù)元素交換原理快速排序算法的原理與步驟快速排序算法的實現(xiàn)快速排序?qū)儆谝环N交換排序法，類似冒泡排序。簡要復(fù)習(xí)冒泡排序算法原理。由學(xué)生自行寫出冒泡排序算法的程序，教師給出參考程序。強調(diào)交換結(jié)合下面的示例進行講解，先講解示例的排序過程，再仔細講解快速排序原理。建議：先以該圖為例講解快速排序原理，讓同學(xué)們有個大致理解。先用一次快速排序，再針對兩邊的數(shù)據(jù)分別應(yīng)用插入排序。簡要復(fù)習(xí)插入式排序算法原理與相關(guān)程序。找到一次快排后樞軸的位置。對前半部分插入排序?qū)蟀氩糠植迦肱判驈膆igh端開始比較如果后面的數(shù)據(jù)比樞軸數(shù)據(jù)大，high指針前移。否則，與key值位置數(shù)據(jù)交換。low指針遞增交換方向，由low端開始比較如果前面的數(shù)據(jù)比樞軸數(shù)據(jù)小，low指針后移。否則，與key值位置數(shù)據(jù)交換。high指針遞減交換方向，由high端開始比較放置樞軸數(shù)據(jù)元素返回樞軸數(shù)據(jù)位置由學(xué)生根據(jù)以前的課程內(nèi)容自行完成。

課外作業(yè)：1.復(fù)習(xí)本次課所授的相關(guān)知識內(nèi)容；2．預(yù)習(xí)下講相關(guān)知識。教學(xué)反思、總結(jié)：