快速排序算法高校試講PPT

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

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

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