1、算法設(shè)計與分析,譚守標(biāo) 安徽大學(xué) 電子學(xué)院 2007.9,第六章 快速排序,快速排序算法 快速排序的隨機化版本 程序演示及說明 算法性能分析（三種情況）,問題：,1、什么是分治法？ 2、什么是排序？ 3、用分治法解決排序問題的思想是什么？,1.算法的提出：由C.A.R.Hoare提出。 2.定義：快速排序(quick sort)又稱分劃交換排序。,一、快速排序算法的基本概念,3.其解決排序問題的基本思路：使用分治法。 基本步驟： a.分解：數(shù)組Ap.r被劃分為兩個非空子數(shù)組Ap.q和Aq+1.r,使得Ap.q的每一個元素都小于等于Aq+1.r的元素。 b.解決：通過遞歸調(diào)用快速排序?qū)ψ訑?shù)組Ap

2、.q和Aq+1.r進行排序。 c.合并：快速排序無需合并操作。,快速排序算法: QUICKSORT(A,p,r) 1 if pr 2 then q PARTITION(A,p,r) 3 QUICKSORT(A,p,q) 4 QUICKSORT(A,q+1,r),算法描述,二、快速排序的分解、解決過程,1. 分解：調(diào)用PARTITION對數(shù)組Ap.r進行劃分。 分解方法：在待排序的數(shù)組Ap.r中選擇一個元素作為分劃元素，也稱為主元(最簡單的做法是選擇數(shù)組的第一個元素為主元)。 經(jīng)過一趟劃分操作將數(shù)組重新排列，將小于主元的元素放在原數(shù)組的底部區(qū)域，把大于主元的元素放在原數(shù)組的頂部區(qū)域。 示意圖：

3、主元 PARTITION,底部區(qū)域,頂部區(qū)域,2.解決：通過遞歸調(diào)用快速排序?qū)ψ訑?shù)組Ap.q和Aq+1.r排序，直到劃分得到的子數(shù)組中只有一個元素時，遞歸調(diào)用結(jié)束。 3.合并：快速排序經(jīng)過一趟劃分操作將數(shù)組分解成兩個子數(shù)組，且位于底部區(qū)域的元素均不大于主元，位于頂部區(qū)域的元素均不小于主元，所以，一旦兩個子數(shù)組已經(jīng)完成分別排序，整個數(shù)組自然成為有序序列。,PARTITION實例：,i,j,i,i,j,j,i,j,j,i,(a),(b),(c),(d),(e),Ap.r,Ap.q,Aq+1.r,一次劃分結(jié)束,主元,return,PARTITION(A,p,r) 1 x Ap 2 i p-1 3 j

4、 r+1 4 while TRUE /三次循環(huán)就把前一個數(shù)組搞定了 5 do repeat j j-1 6 until Ajx /后面小于主元 7 repeat i i+1 8 until Aix /前面的大于主元 9 if ij 10 then exchange Ai Aj 11 else return j,劃分的正確性,a.下標(biāo)i和j不會指向數(shù)組A中區(qū)間p.r以外的元素。 b.當(dāng)PARTITION結(jié)束時，下標(biāo)j不等于r。 c.當(dāng)PARTITION結(jié)束時，Ap.j中的每個元素都小于等于Aj+1.r中的每個元素。,性能分析,最壞情況劃分： T(n)=T(n-1)+(n),最佳情況劃分： T(n

5、)=2T(n/2)+(n)=(nlgn),常數(shù)比例劃分： T(n)=T(an)+T(1-a)n)+(n)=(nlgn),平均情況劃分： 直覺：(nlgn) 差的劃分可以吸收到好的劃分中。,三、快速排序的隨機化版本,1. 隨機化版本的提出 2.在快速排序中使用隨機選擇策略 在快速排序算法的每一步中，當(dāng)數(shù)組還沒有被劃分時，可將元素Ap與Ap.r中隨機選出的一個元素交換后再執(zhí)行PARTITION。 3.使用隨機化版本的優(yōu)點,隨機化版本的算法,RANDOMIZED-PARTITION 1 i RANDOM(p,r) 2 exchange Ap Ai 3 return PARTITION(p,q,r) RANDOMIZED-QUICKSORT(A,p,r) 1 if pr 2 then q RANDOMIZED-PARTITION(A,p,r) 3 RANDOMIZED-QUICKSORT(A,p,q) 4 RANDOMIZED- QUICKSORT(A,q+1,r),四、快速排序分析,(n-1) =,n -2(n-1),最壞情況分析,平均情況分析 兩個假設(shè)： （1）假設(shè)所有輸入數(shù)據(jù)均不同； （2）假定每個排列出現(xiàn)是等概率的；,關(guān)于劃分過程的