算法設計與分析(fēnxī)快速排序第一頁，共28頁。第六章快速(kuàisù)排序快速排序算法快速排序的隨機化版本程序演示及說明(shuōmíng)算法性能分析（三種情況）第二頁，共28頁。問題(wèntí)：1、什么是分治(fēnzhì)法？2、什么是排序？3、用分治(fēnzhì)法解決排序問題的思想是什么？第三頁，共28頁。1.算法的提出：由提出。2.定義(dìngyì)：快速排序(quicksort)又稱分劃交換排序。一、快速(kuàisù)排序算法的基本概念第四頁，共28頁。3.其解決(jiějué)排序問題的基本思路：使用分治法?；静襟E：a.分解：數(shù)組A[p..r]被劃分為兩個非空子數(shù)組A[p..q]和A[q+1..r],使得A[p..q]的每一個元素都小于等于A[q+1..r]的元素。b.解決(jiějué)：通過遞歸調(diào)用快速排序?qū)ψ訑?shù)組A[p..q]和A[q+1..r]進行排序。c.合并：快速排序無需合并操作。第五頁，共28頁?？焖倥判?páixù)算法:QUICKSORT(A,p,r)1ifp<r2thenqPARTITION(A,p,r)3QUICKSORT(A,p,q)4QUICKSORT(A,q+1,r)算法(suànfǎ)描述第六頁，共28頁。二、快速排序的分解(fēnjiě)、解決過程1.分解：調(diào)用PARTITION對數(shù)組A[p..r]進行劃分。分解方法(fāngfǎ)：在待排序的數(shù)組A[p..r]中選擇一個元素作為分劃元素，也稱為主元(最簡單的做法是選擇數(shù)組的第一個元素為主元)。經(jīng)過一趟劃分操作將數(shù)組重新排列，將小于主元的元素放在原數(shù)組的底部區(qū)域，把大于主元的元素放在原數(shù)組的頂部區(qū)域。示意圖：主元PARTITION75641233底部區(qū)域(qūyù)頂部區(qū)域73146235第七頁，共28頁。2.解決：通過遞歸調(diào)用快速排序?qū)ψ訑?shù)組A[p..q]和A[q+1..r]排序，直到劃分得到的子數(shù)組中只有一個元素時，遞歸調(diào)用結(jié)束(jiéshù)。3.合并：快速排序經(jīng)過一趟劃分操作將數(shù)組分解成兩個子數(shù)組，且位于底部區(qū)域的元素均不大于主元，位于頂部區(qū)域的元素均不小于主元，所以，一旦兩個子數(shù)組已經(jīng)完成分別排序，整個數(shù)組自然成為有序序列。第八頁，共28頁。PARTITION實例(shílì)：ijiijjijji(a)(b)(c)(d)(e)A[p..r]A[p..q]A[q+1..r]一次劃分(huàfēn)結(jié)束主元return7314623573146235751462337514623375641233第九頁，共28頁。PARTITION(A,p,r)1xA[p]2ip-13jr+14whileTRUE//三次循環(huán)(xúnhuán)就把前一個數(shù)組搞定了5dorepeatjj-16untilA[j]≤x//后面小于主元7repeatii+18untilA[i]≥x//前面的大于主元9ifi<j10thenexchangeA[i]A[j]11elsereturnj第十頁，共28頁。劃分(huàfēn)的正確性a.下標i和j不會指向數(shù)組A中區(qū)間[p..r]以外(yǐwài)的元素。b.當PARTITION結(jié)束時，下標j不等于r。c.當PARTITION結(jié)束時，A[p..j]中的每個元素都小于等于A[j+1..r]中的每個元素。第十一頁，共28頁。性能(xìngnéng)分析最壞情況(qíngkuàng)劃分：T(n)=T(n-1)+(n)第十二頁，共28頁。最佳(zuìjiā)情況劃分：T(n)=2T(n/2)+(n)=(nlgn)第十三頁，共28頁。常數(shù)比例(bǐlì)劃分：T(n)=T(an)+T((1-a)n)+(n)=(nlgn)第十四頁，共28頁。平均情況劃分(huàfēn)：直覺：(nlgn)差的劃分(huàfēn)可以吸收到好的劃分(huàfēn)中。第十五頁，共28頁。三、快速(kuàisù)排序的隨機化版本1.隨機化版本的提出2.在快速排序中使用隨機選擇策略在快速排序算法的每一步中，當數(shù)組還沒有被劃分時，可將元素A[p]與A[p..r]中隨機選出的一個元素交換(jiāohuàn)后再執(zhí)行PARTITION。3.使用隨機化版本的優(yōu)點第十六頁，共28頁。隨機化版本(bǎnběn)的算法RANDOMIZED-PARTITION1iRANDOM(p,r)2exchangeA[p]A[i]3returnPARTITION(p,q,r)RANDOMIZED-QUICKSORT(A,p,r)1ifp<r2thenqRANDOMIZED-PARTITION(A,p,r)3RANDOMIZED-QUICKSORT(A,p,q)4RANDOMIZED-QUICKSORT(A,q+1,r)第十七頁，共28頁。四、快速(kuàisù)排序分析(n-1)2=

n2-2(n-1)最壞情況(qíngkuàng)分析第十八頁，共28頁。第十九頁，共28頁。平均情況分析兩個假設： （1）假設所有輸入數(shù)據(jù)(shùjù)均不同； （2）假定每個排列出現(xiàn)是等概率的；第二十頁，共28頁。關(guān)于劃分過程的分析關(guān)于平均情況性態(tài)的一個(yīɡè)遞歸式解遞歸式上述和式的緊確界第二十一頁，共28頁。關(guān)于劃分過程(guòchéng)的分析第二十二頁，共28頁。第二十三頁，共28頁。（2）假定每個排列出現(xiàn)是等概率的；T(n)=T(n-1)+(n)三、快速(kuàisù)排序的隨機化版本7repeatii+1第二十三頁，共28頁。r]中隨機選出的一個元素交換(jiāohuàn)后再執(zhí)行PARTITION。當PARTITION結(jié)束時，下標j不等于r。5dorepeatjj-1（1）假設所有輸入數(shù)據(jù)(shùjù)均不同；解決：通過遞歸調(diào)用快速排序?qū)ψ訑?shù)組A[p.T(n)=T(n-1)+(n)PARTITION實例(shílì)：分解方法(fāngfǎ)：在待排序的數(shù)組A[p.差的劃分(huàfēn)可以吸收到好