算法設(shè)計(jì)與分析快速排序

算法設(shè)計(jì)與分析快速排序第一頁，共二十八頁，2022年，8月28日第六章快速排序快速排序算法快速排序的隨機(jī)化版本程序演示及說明算法性能分析（三種情況）第二頁，共二十八頁，2022年，8月28日問題：1、什么是分治法？2、什么是排序？3、用分治法解決排序問題的思想是什么？第三頁，共二十八頁，2022年，8月28日1.算法的提出：由提出。2.定義：快速排序(quicksort)又稱分劃交換排序。一、快速排序算法的基本概念第四頁，共二十八頁，2022年，8月28日3.其解決排序問題的基本思路：使用分治法。基本步驟：a.分解：數(shù)組A[p..r]被劃分為兩個非空子數(shù)組A[p..q]和A[q+1..r],使得A[p..q]的每一個元素都小于等于A[q+1..r]的元素。b.解決：通過遞歸調(diào)用快速排序?qū)ψ訑?shù)組A[p..q]和A[q+1..r]進(jìn)行排序。c.合并：快速排序無需合并操作。第五頁，共二十八頁，2022年，8月28日快速排序算法:QUICKSORT(A,p,r)1ifp<r2thenqPARTITION(A,p,r)3QUICKSORT(A,p,q)4QUICKSORT(A,q+1,r)算法描述第六頁，共二十八頁，2022年，8月28日二、快速排序的分解、解決過程1.分解：調(diào)用PARTITION對數(shù)組A[p..r]進(jìn)行劃分。

分解方法：在待排序的數(shù)組A[p..r]中選擇一個元素作為分劃元素，也稱為主元(最簡單的做法是選擇數(shù)組的第一個元素為主元)。經(jīng)過一趟劃分操作將數(shù)組重新排列，將小于主元的元素放在原數(shù)組的底部區(qū)域，把大于主元的元素放在原數(shù)組的頂部區(qū)域。示意圖：主元PARTITION75641233底部區(qū)域頂部區(qū)域73146235第七頁，共二十八頁，2022年，8月28日2.解決：通過遞歸調(diào)用快速排序?qū)ψ訑?shù)組A[p..q]和A[q+1..r]排序，直到劃分得到的子數(shù)組中只有一個元素時，遞歸調(diào)用結(jié)束。3.合并：快速排序經(jīng)過一趟劃分操作將數(shù)組分解成兩個子數(shù)組，且位于底部區(qū)域的元素均不大于主元，位于頂部區(qū)域的元素均不小于主元，所以，一旦兩個子數(shù)組已經(jīng)完成分別排序，整個數(shù)組自然成為有序序列。第八頁，共二十八頁，2022年，8月28日PARTITION實(shí)例：ijiijjijji(a)(b)(c)(d)(e)A[p..r]A[p..q]A[q+1..r]一次劃分結(jié)束主元return7314623573146235751462337514623375641233第九頁，共二十八頁，2022年，8月28日PARTITION(A,p,r)1xA[p]2ip-13jr+14whileTRUE//三次循環(huán)就把前一個數(shù)組搞定了5dorepeatjj-16untilA[j]≤x//后面小于主元7repeatii+18untilA[i]≥x//前面的大于主元9ifi<j10thenexchangeA[i]A[j]11elsereturnj第十頁，共二十八頁，2022年，8月28日劃分的正確性a.下標(biāo)i和j不會指向數(shù)組A中區(qū)間[p..r]以外的元素。b.當(dāng)PARTITION結(jié)束時，下標(biāo)j不等于r。c.當(dāng)PARTITION結(jié)束時，A[p..j]中的每個元素都小于等于A[j+1..r]中的每個元素。第十一頁，共二十八頁，2022年，8月28日性能分析最壞情況劃分：T(n)=T(n-1)+(n)第十二頁，共二十八頁，2022年，8月28日最佳情況劃分：T(n)=2T(n/2)+(n)=(nlgn)第十三頁，共二十八頁，2022年，8月28日常數(shù)比例劃分：T(n)=T(an)+T((1-a)n)+(n)=(nlgn)第十四頁，共二十八頁，2022年，8月28日平均情況劃分：直覺：(nlgn)差的劃分可以吸收到好的劃分中。第十五頁，共二十八頁，2022年，8月28日三、快速排序的隨機(jī)化版本

1.隨機(jī)化版本的提出

2.在快速排序中使用隨機(jī)選擇策略

在快速排序算法的每一步中，當(dāng)數(shù)組還沒有被劃分時，可將元素A[p]與A[p..r]中隨機(jī)選出的一個元素交換后再執(zhí)行PARTITION。

3.使用隨機(jī)化版本的優(yōu)點(diǎn)第十六頁，共二十八頁，2022年，8月28日隨機(jī)化版本的算法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)第十七頁，共二十八頁，2022年，8月28日四、快速排序分析(n-1)2=

n2-2(n-1)最壞情況分析第十八頁，共二十八頁，2022年，8月28日第十九頁，共二十八頁，2022年，8月28日平均情況分析兩個假設(shè)： （1）假設(shè)所有輸入數(shù)據(jù)均不同； （2）假定每個排列出現(xiàn)是等概率的；第二十頁，共二十八頁，2022年，8月28日關(guān)于劃分過程的分析關(guān)于平均情況性態(tài)的一個遞歸式解遞歸式上述和式的緊確界第二十一頁，共二十八頁，2022年，8月28日關(guān)于劃分過程的分析第二十二頁，共二十八頁，2022年，8月28日第二十三頁，共二十八頁，2022年，8月28日關(guān)于平均情況性態(tài)的一