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

算法設(shè)計與分析快速排序第一頁，共二十八頁，編輯于2023年，星期三第六章快速排序快速排序算法快速排序的隨機化版本程序演示及說明算法性能分析（三種情況）第二頁，共二十八頁，編輯于2023年，星期三問題：1、什么是分治法？2、什么是排序？3、用分治法解決排序問題的思想是什么？第三頁，共二十八頁，編輯于2023年，星期三1.算法的提出：由C.A.R.Hoare提出。2.定義：快速排序(quicksort)又稱分劃交換排序。一、快速排序算法的基本概念第四頁，共二十八頁，編輯于2023年，星期三3.其解決排序問題的基本思路：使用分治法?；静襟E：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]進行排序。c.合并：快速排序無需合并操作。第五頁，共二十八頁，編輯于2023年，星期三快速排序算法:QUICKSORT(A,p,r)1ifp<r2thenqPARTITION(A,p,r)3QUICKSORT(A,p,q)4QUICKSORT(A,q+1,r)算法描述第六頁，共二十八頁，編輯于2023年，星期三二、快速排序的分解、解決過程1.分解：調(diào)用PARTITION對數(shù)組A[p..r]進行劃分。分解方法：在待排序的數(shù)組A[p..r]中選擇一個元素作為分劃元素，也稱為主元(最簡單的做法是選擇數(shù)組的第一個元素為主元)。經(jīng)過一趟劃分操作將數(shù)組重新排列，將小于主元的元素放在原數(shù)組的底部區(qū)域，把大于主元的元素放在原數(shù)組的頂部區(qū)域。示意圖：主元PARTITION75641233底部區(qū)域頂部區(qū)域73146235第七頁，共二十八頁，編輯于2023年，星期三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ù)組自然成為有序序列。第八頁，共二十八頁，編輯于2023年，星期三PARTITION實例：ijiijjijji(a)(b)(c)(d)(e)A[p..r]A[p..q]A[q+1..r]一次劃分結(jié)束主元return7314623573146235751462337514623375641233第九頁，共二十八頁，編輯于2023年，星期三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第十頁，共二十八頁，編輯于2023年，星期三劃分的正確性a.下標i和j不會指向數(shù)組A中區(qū)間[p..r]以外的元素。b.當PARTITION結(jié)束時，下標j不等于r。c.當PARTITION結(jié)束時，A[p..j]中的每個元素都小于等于A[j+1..r]中的每個元素。第十一頁，共二十八頁，編輯于2023年，星期三性能分析最壞情況劃分：T(n)=T(n-1)+(n)第十二頁，共二十八頁，編輯于2023年，星期三最佳情況劃分：T(n)=2T(n/2)+(n)=(nlgn)第十三頁，共二十八頁，編輯于2023年，星期三常數(shù)比例劃分：T(n)=T(an)+T((1-a)n)+(n)=(nlgn)第十四頁，共二十八頁，編輯于2023年，星期三平均情況劃分：直覺：(nlgn)差的劃分可以吸收到好的劃分中。第十五頁，共二十八頁，編輯于2023年，星期三三、快速排序的隨機化版本

1.隨機化版本的提出

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

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

3.使用隨機化版本的優(yōu)點第十六頁，共二十八頁，編輯于2023年，星期三隨機化版本的算法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)第十七頁，共二十八頁，編輯于2023年，星期三四、快速排序分析(n-1)2=

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