算法设计与分析快速排序精.ppt

《算法设计与分析快速排序精.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析快速排序精.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析快速排序算法设计与分析快速排序第1页，本讲稿共28页第六章第六章 快速排序快速排序n快速排序算法快速排序算法n快速排序的随机化版本快速排序的随机化版本n程序演示及说明程序演示及说明n算法性能分析（三种情况）算法性能分析（三种情况）第2页，本讲稿共28页问题：问题：n1 1、什么是分治法？、什么是分治法？n2 2、什么是排序？、什么是排序？n3 3、用分治法解决排序问题的思想是什么、用分治法解决排序问题的思想是什么？第3页，本讲稿共28页n1.1.算法的提出：由算法的提出：由C.A.R.HoareC.A.R.Hoare提出。提出。n2.2.定义：快速排序定义：快速排序(quick

2、sort)(quick sort)又称分划交又称分划交换排序。换排序。一、快速排序算法的基本概念一、快速排序算法的基本概念第4页，本讲稿共28页n3.3.其解决排序问题的基本思路：使用分治其解决排序问题的基本思路：使用分治法。法。基本步骤：基本步骤：na.a.分解：数组分解：数组Ap.rAp.r被划分为两个非空子数被划分为两个非空子数组组Ap.qAp.q和和Aq+1.r,Aq+1.r,使得使得Ap.qAp.q的每一个的每一个元素都小于等于元素都小于等于Aq+1.rAq+1.r的元素。的元素。nb.b.解决：通过递归调用快速排序对子数组解决：通过递归调用快速排序对子数组Ap.qAp.q和和Aq+

3、1.rAq+1.r进行排序。进行排序。nc.c.合并：快速排序无需合并操作。合并：快速排序无需合并操作。第5页，本讲稿共28页n快速排序算法快速排序算法:n QUICKSORT(A,p,r)QUICKSORT(A,p,r)n 1 if pr 1 if pr n 2 then q PARTITION(A,p,r)2 then q PARTITION(A,p,r)n 3 QUICKSORT(A,p,q)3 QUICKSORT(A,p,q)n 4 QUICKSORT(A,q+1,r)4 QUICKSORT(A,q+1,r)算法描述算法描述第6页，本讲稿共28页二、快速排序的分解、解决过程二、快速排序

4、的分解、解决过程n1.1.分解：调用分解：调用PARTITIONPARTITION对数组对数组Ap.rAp.r进行划分。进行划分。分解方法：在待排序的数组分解方法：在待排序的数组Ap.rAp.r中选择一个元素作为中选择一个元素作为分划元素分划元素，也称为也称为主元主元(最简单的做法是选择数组的第一个元素为主元最简单的做法是选择数组的第一个元素为主元)。经过一经过一趟划分操作将数组重新排列，将小于主元的元素放在原数组的底部区域，趟划分操作将数组重新排列，将小于主元的元素放在原数组的底部区域，把大于主元的元素放在原数组的顶部区域。把大于主元的元素放在原数组的顶部区域。示意图：示意图：主元主元 PA

5、RTITIONPARTITION75641233底部区域底部区域顶顶部区域部区域73146235第7页，本讲稿共28页n2.2.解决：通过递归调用快速排序对子数组解决：通过递归调用快速排序对子数组Ap.qAp.q和和Aq+1.rAq+1.r排序，直到划分得到的子数组中只有排序，直到划分得到的子数组中只有一个元素时，递归调用结束。一个元素时，递归调用结束。n3.3.合并：快速排序经过一趟划分操作将数组分解成合并：快速排序经过一趟划分操作将数组分解成两个子数组，且位于底部区域的元素均不大于主元，两个子数组，且位于底部区域的元素均不大于主元，位于顶部区域的元素均不小于主元，所以，一旦两位于顶部区域的

6、元素均不小于主元，所以，一旦两个子数组已经完成分别排序，整个数组自然成为有个子数组已经完成分别排序，整个数组自然成为有序序列。序序列。第8页，本讲稿共28页PARTITIONPARTITION实例：实例：i ij ji ii ij jj ji ij jj ji i(a)(a)(b)(b)(c)(c)(d)(d)(e)(e)Ap.rAp.rAp.qAp.qAq+1.rAq+1.r一次划分一次划分结结束束主元主元returnreturn7314623573146235751462337514623375641233第9页，本讲稿共28页nPARTITION(A,p,r)PARTITION(A,p,

7、r)n1 x Ap1 x Apn2 i p-12 i p-1n3 j r+13 j r+1n4 while TRUE /4 while TRUE /三次循环就把前一个数组搞定了三次循环就把前一个数组搞定了n5 do repeat j j-15 do repeat j j-1n6 until Ajx/6 until Ajx/后面小于主元后面小于主元n7 repeat i i+1 7 repeat i i+1 n8 until Aix/8 until Aix/前面的大于主元前面的大于主元n9 if ij 9 if ij n10 then exchange Ai Aj10 then exchange

8、 Ai Ajn11 else return j11 else return j第10页，本讲稿共28页划分的正确性划分的正确性 na.a.下标下标i i和和j j不会指向数组不会指向数组A A中区间中区间p.rp.r以以外的元素。外的元素。nb.b.当当PARTITIONPARTITION结束时，下标结束时，下标j j不等于不等于r r。nc.c.当当PARTITIONPARTITION结束时，结束时，Ap.jAp.j中的每个中的每个元素都小于等于元素都小于等于Aj+1.rAj+1.r中的每个元素。中的每个元素。第11页，本讲稿共28页性能分析性能分析 n最坏情况划分：最坏情况划分：T(n)=

9、T(n-1)+T(n)=T(n-1)+(n)(n)第12页，本讲稿共28页n最佳情况划分：最佳情况划分：T(n)=2T(n/2)+T(n)=2T(n/2)+(n)=(n)=(nlgn)(nlgn)第13页，本讲稿共28页n常数比例划分：常数比例划分：T(n)=T(an)+T(1-a)n)+T(n)=T(an)+T(1-a)n)+(n)=(n)=(nlgn)(nlgn)第14页，本讲稿共28页n平均情况划分：平均情况划分：直觉：直觉：(nlgn)(nlgn)差的划分可以吸收到好的划分中。差的划分可以吸收到好的划分中。第15页，本讲稿共28页三、快速排序的随机化版本三、快速排序的随机化版本n 1.

10、1.随机化版本的提出随机化版本的提出n 2.2.在快速排序中使用随机选择策略在快速排序中使用随机选择策略n 在快速排序算法的每一步中，当数组在快速排序算法的每一步中，当数组还没有被划分时，可将元素还没有被划分时，可将元素ApAp与与Ap.rAp.r中随机选出的一个元素交换后再执行中随机选出的一个元素交换后再执行PARTITIONPARTITION。n 3.3.使用随机化版本的优点使用随机化版本的优点第16页，本讲稿共28页随机化版本的算法随机化版本的算法nRANDOMIZED-PARTITIONRANDOMIZED-PARTITIONn1 i RANDOM(p,r)1 i RANDOM(p,r

11、)n2 exchange Ap Ai2 exchange Ap Ain3 return PARTITION(p,q,r)3 return PARTITION(p,q,r)nRANDOMIZED-QUICKSORT(A,p,r)RANDOMIZED-QUICKSORT(A,p,r)n1 if pr1 if prn2 then q RANDOMIZED-PARTITION(A,p,r)2 then q RANDOMIZED-PARTITION(A,p,r)n3 RANDOMIZED-QUICKSORT(A,p,q)3 RANDOMIZED-QUICKSORT(A,p,q)n4 RANDOMIZED

12、-QUICKSORT(A,q+1,r)4 RANDOMIZED-QUICKSORT(A,q+1,r)第17页，本讲稿共28页四、快速排序分析四、快速排序分析(n-1)=n-2(n-1)n最坏情况分析最坏情况分析第18页，本讲稿共28页第19页，本讲稿共28页n平均情况分析平均情况分析两个假设：两个假设：（1 1）假设所有输入数据均不同；）假设所有输入数据均不同；（2 2）假定每个排列出现是等概率的；）假定每个排列出现是等概率的；第20页，本讲稿共28页n关于划分过程的分析关于划分过程的分析n关于平均情况性态的一个递归式关于平均情况性态的一个递归式n解递归式解递归式n上述和式的紧确界上述和式的紧确界第21页，本讲稿共28页关于划分过程的分析关于划分过程的分析第22页，本讲稿共28页第23页，本讲稿共28页关于平均情况性态的一个递归式关于平均情况性态的一个递归式第24页，本讲稿共28页解递归式解递归式第25页，本讲稿共28页第26页，本讲稿共28页上述和式的紧确界上述和式的紧确界第27页，本讲稿共28页The EndThe EndnThank you!Thank you!第28页，本讲稿共28页