快速排序?qū)W習(xí)教案

1、會(huì)計(jì)學(xué)1快速快速(kui s)排序排序第一頁(yè)，共24頁(yè)?？焖?kui s)排序?qū)肟焖?kui s)排序思想快速排序講解快速排序算法分析練習(xí)題退出第1頁(yè)/共23頁(yè)第二頁(yè)，共24頁(yè)。請(qǐng)同學(xué)們使用(shyng)冒泡排序的方法將下列數(shù)據(jù)排序：（從小到大）21 25 49 16 25 06 目錄(ml)第2頁(yè)/共23頁(yè)第三頁(yè)，共24頁(yè)。初始狀態(tài)第一次交換(jiohun)結(jié)束目錄(ml)第3頁(yè)/共23頁(yè)第四頁(yè)，共24頁(yè)。第二次交換(jiohun)第二次交換(jiohun)結(jié)束目錄第4頁(yè)/共23頁(yè)第五頁(yè)，共24頁(yè)。第三次交換(jiohun)結(jié)束第二次交換(jiohun)結(jié)束第四次交換(jiohun)結(jié)束目

2、錄第5頁(yè)/共23頁(yè)第六頁(yè)，共24頁(yè)。第六次交換(jiohun)結(jié)束第五次交換(jiohun)結(jié)束請(qǐng)同學(xué)(tng xu)們說(shuō)說(shuō)冒泡排序是如何工作的目錄第6頁(yè)/共23頁(yè)第七頁(yè)，共24頁(yè)。冒泡排序的基本(jbn)做法：思考：在數(shù)據(jù)為以下排列時(shí)，冒泡的排序效果好不好？49 25 25 21 16 06 第7頁(yè)/共23頁(yè)第八頁(yè)，共24頁(yè)。112112)(2/ ) 1(3)( 3)(2/ ) 1()(nininOnninnOnnin移動(dòng)次數(shù)的最大值比較次數(shù)的最大值目錄(ml)第8頁(yè)/共23頁(yè)第九頁(yè)，共24頁(yè)。從直觀上49移動(dòng)到最終(zu zhn)的位置經(jīng)過(guò)了n-1次比較和交換49 25 25 21 16

3、0606 16 21 25 25 49能不能不經(jīng)過(guò)(jnggu)n-1次比較和交換呢？不能？這是由于冒泡排序中需要相鄰的元素兩兩比較、交換目錄第9頁(yè)/共23頁(yè)第十頁(yè)，共24頁(yè)。目錄第10頁(yè)/共23頁(yè)第十一頁(yè)，共24頁(yè)。以21為中心(zhngxn)元素劃分(hu fn)可得：以06、49為中心元素劃分可得：目錄第11頁(yè)/共23頁(yè)第十二頁(yè)，共24頁(yè)。 選取中心元素(yun s)的問(wèn)題選取(xunq)第一個(gè)數(shù)為中心元素 如何劃分問(wèn)題 如何重復(fù)步驟將所有數(shù)據(jù)排序使用遞歸目錄第12頁(yè)/共23頁(yè)第十三頁(yè)，共24頁(yè)。當(dāng)已知中心元素的前提下，怎樣將其他元素劃分(hu fn)好？（即：大于中心點(diǎn)在之后，小于中心

4、點(diǎn)在之前）需要(xyo)解決的問(wèn)題i012345i=0i=1j=5j=5ji=1j=3i=1j=4i=2j=3i=2j=2算法終止目錄第13頁(yè)/共23頁(yè)第十四頁(yè)，共24頁(yè)。請(qǐng)同學(xué)(tng xu)們思考該算法(sun f)有沒(méi)有可以改進(jìn)的地方目錄第14頁(yè)/共23頁(yè)第十五頁(yè)，共24頁(yè)。i012345i=0i=1j=5j=5ji=1j=3i=1j=4i=2j=3i=2j=2算法(sun f)終止通過(guò)動(dòng)畫(huà)，可以看出每次中心元素都要交換。根據(jù)劃分(hu fn)的思想最后位置一定是中心元素可以申請(qǐng)一個(gè)變量保存中心元素，以避免交換目錄第15頁(yè)/共23頁(yè)第十六頁(yè)，共24頁(yè)。i=left;j=right;int

5、 temp=aleft;do/從右向左找第1個(gè)不小于中心元素(yun s)的位置jwhile( aj temp & ij) j-;if(ij)a I = a j ;i+;ai=temp;left,right用于限定要排序數(shù)列(shli)的范圍,temp即為中心元素程序填空當(dāng)前元素小于中心元素結(jié)束循環(huán)時(shí)，應(yīng)當(dāng)在中心元素的左邊移至左邊目錄第16頁(yè)/共23頁(yè)第十七頁(yè)，共24頁(yè)。/從左向右找第1個(gè)不大于中心元素(yun s)的位置iwhile(aitemp & ij ) i+;if(ij)aj=ai;j-;while(ij);ai=temp; /將中心元素(yun s)t填入最終位置程

6、序(chngx)填空目錄第17頁(yè)/共23頁(yè)第十八頁(yè)，共24頁(yè)。i=left;j=right;int temp=aleft;ai=temp;quicksort(a,left,i-1);quicksort(a,i+1,right);目錄第18頁(yè)/共23頁(yè)第十九頁(yè)，共24頁(yè)。void quicksort(int a,int left,int right)int i,j;if(lefttemp & ij)j-;if(ij)ai=aj;i+;目錄(ml)第19頁(yè)/共23頁(yè)第二十頁(yè)，共24頁(yè)。while(aitemp & ij)i+;if(ij)aj=ai;j-;while(ij);ai=

7、temp;quicksort(a,left,i-1);quicksort(a,i+1,right);目錄(ml)第20頁(yè)/共23頁(yè)第二十一頁(yè)，共24頁(yè)。思考：當(dāng)數(shù)據(jù)有序的情況下，快速排序(pi x)的效率如何？快速排序(pi x)的最壞時(shí)間復(fù)雜度為O(n2)06 16 21 25 25 49例快速排序的最好時(shí)間復(fù)雜度為O(nlog2n)快速排序的平均時(shí)間復(fù)雜度為O(nlog2n)快速排序是不穩(wěn)定的排序方法目錄第21頁(yè)/共23頁(yè)第二十二頁(yè)，共24頁(yè)。1）在快速排序方法中，進(jìn)行每次劃分時(shí)，是從當(dāng)前待排序區(qū)間(q jin) 的_ 向_依次查找出處于逆序的元素并交換之，最后將 中心元素交換到一個(gè)確定位

8、置，從而以該位置把當(dāng)前區(qū)間(q jin)劃分為前后 兩端(lin dun)中間(zhngjin)2）假定一組記錄的關(guān)鍵字為 (46,79,56,38,40,80)，對(duì)其進(jìn)行快速 排序的一次劃分的結(jié)果為_(kāi)。38 40 46 56 79 843）快速排序在_情況下效率最低，在_情況下最易發(fā)揮其長(zhǎng)處。排序?qū)ο笠呀?jīng)按其關(guān)鍵字從小到大排好每次劃分對(duì)象定位后，左側(cè)子序列與右 側(cè)子序列長(zhǎng)度相同4）快速排序在平均情況下的時(shí)間復(fù)雜度為_(kāi) ，在最壞 情況下的時(shí)間復(fù)雜度為_(kāi)。 O(nlog2n)O(n2)目錄第22頁(yè)/共23頁(yè)第二十三頁(yè)，共24頁(yè)。NoImage內(nèi)容(nirng)總結(jié)會(huì)計(jì)學(xué)。第1頁(yè)/共23頁(yè)。目錄。1）尋找一個(gè)中心元素（通常為第一個(gè)數(shù)）。當(dāng)已知中心元素的前提下，怎樣將其他元素劃分(hu fn)好。（即：大于中心點(diǎn)在之后，小于中心點(diǎn)在之前