1、試講：快速排序目 錄問題導(dǎo)入思想解讀案例講解123代碼實現(xiàn)總結(jié)作業(yè)性能分析4561、問題導(dǎo)入：為什么會有快速排序？傳統(tǒng)排序的缺點傳統(tǒng)排序：冒泡排序選擇排序插入排序兩兩比較傳統(tǒng)排序的缺點2、核心思想：分治與遞歸分治思想3、案例講解：個無序整數(shù)快速排序基本步驟遞歸的4個步驟1、選定Pivot中心軸2、將大于Pivot的數(shù)字放在Pivot的右邊3、將小于Pivot的數(shù)字放在Pivot的左邊4、分別對左右子序列重復(fù)前三步操作案例講解3897162606093897162606093897案例講解389716260609LR38Pivot9716260609LR0938(Pivot)0638(Pivot

2、)1638(Pivot)2609（Pivot）1609（Pivot）0616(Pivot)案例講解1626060938973897162606093897案例講解4、代碼實現(xiàn)：C語言代碼實現(xiàn)代碼實現(xiàn)：一趟劃分函數(shù)int Partition(SqList &L, int left, int right) L.rleft=l.r0; pivotkey=l.r0.key; while(left=pivotkey)-right;L.rleft=L.rright; while(leftright&L.rleft.key=pivotkey)+left; L.rright=L.rleft; while(le

3、ftright) L.rleft=pivotkey; reture left;void QSort(SqList &L,int left,int right)if(leftright) pivotloc=Partition(L,left,right); Qsort(L,left, pivotloc-1);Qsort(L,pivotloc+1,right);代碼實現(xiàn)：快速排序函數(shù)5、性能總結(jié)：時空分析最好：劃分后，左子序列和右子序列的長度相同最壞：有序，遞歸樹成為單支樹，每次劃分只得到一個比上一次少一個對象的子序列，必須經(jīng)過n-1趟才能把所有對象定位，而且第i趟需要經(jīng)過n-i次關(guān)鍵碼才能得到第i

4、個對象的安放位置性能總結(jié)：最好最壞場景分析可以證明，平均計算時間是O(nlog2n)。實驗結(jié)果表明：就平均計算時間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個。快速排序是遞歸的，需要有一個棧存放每層遞歸調(diào)用時參數(shù)（新的left和right）。最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，因此，要求存儲開銷為O(log2n)。性能總結(jié)：時間和空間分析時間效率：O(nlog2n)空間效率：O(log2n)-遞歸要用到棧空間不穩(wěn)定性能總結(jié)6、總結(jié)作業(yè)：課程總結(jié)與課后作業(yè)課程總結(jié)解決傳統(tǒng)排序兩兩比較帶來的比較負(fù)荷問題的導(dǎo)入分而治之與遞歸基本思想主要講解了一個位無序數(shù)字序列的案例以及語言代碼的實現(xiàn)案例與代碼時間復(fù)雜度，空間復(fù)雜度，最好、最壞情形性能總結(jié)課后作業(yè)1）在快速排序方法中，進(jìn)行每次劃分時，是從當(dāng)前待排序區(qū)間 的（_） 向（_）依次查找出處于逆序的元素并交換之，最后將 中心元素交換到一個確定位置，從而以該位置把當(dāng)前區(qū)間劃分為前后 2）假定一組記錄的關(guān)鍵字為 (46,79,56,38,40,80)，對其進(jìn)行快速 排序的一次劃分的結(jié)果為（_）。3）快速排序在（_）情況下效率