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

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

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

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