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

2、)1638(Pivot)2609（Pivot）1609（Pivot）0616(Pivot)案例講解1626060938973897162606093897案例講解4、代碼實現：C語言代碼實現代碼實現：一趟劃分函數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);代碼實現：快速排序函數5、性能總結：時空分析最好：劃分后，左子序列和右子序列的長度相同最壞：有序，遞歸樹成為單支樹，每次劃分只得到一個比上一次少一個對象的子序列，必須經過n-1趟才能把所有對象定位，而且第i趟需要經過n-i次關鍵碼才能得到第i

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