《算法设计与分析-7快速排序.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析-7快速排序.ppt（28页珍藏版）》请在三一办公上搜索。
1、算法设计与分析,谭守标安徽大学 电子学院2007.9,第六章 快速排序,快速排序算法快速排序的随机化版本程序演示及说明算法性能分析（三种情况）,问题：,1、什么是分治法？2、什么是排序？3、用分治法解决排序问题的思想是什么？,1.算法的提出：由提出。2.定义：快速排序(quick sort)又称分划交换排序。,一、快速排序算法的基本概念,3.其解决排序问题的基本思路：使用分治法。基本步骤：a.分解：数组Ap.r被划分为两个非空子数组Ap.q和Aq+1.r,使得Ap.q的每一个元素都小于等于Aq+1.r的元素。b.解决：通过递归调用快速排序对子数组Ap.q和Aq+1.r进行排序。c.合并：快速排
2、序无需合并操作。,快速排序算法: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.分解：调用PARTITION对数组Ap.r进行划分。分解方法：在待排序的数组Ap.r中选择一个元素作为分划元素，也称为主元(最简单的做法是选择数组的第一个元素为主元)。经过一趟划分操作将数组重新排列，将小于主元的元素放在原数组的底部区域，把大于主元的元素放在原数组的顶部区域。示意图：主元 PARTITION,底部区域,顶部区域,2.解决：通过递归
3、调用快速排序对子数组Ap.q和Aq+1.r排序，直到划分得到的子数组中只有一个元素时，递归调用结束。3.合并：快速排序经过一趟划分操作将数组分解成两个子数组，且位于底部区域的元素均不大于主元，位于顶部区域的元素均不小于主元，所以，一旦两个子数组已经完成分别排序，整个数组自然成为有序序列。,PARTITION实例：,i,j,i,i,j,j,i,j,j,i,(a),(b),(c),(d),(e),Ap.r,Ap.q,Aq+1.r,一次划分结束,主元,return,PARTITION(A,p,r)1 x Ap2 i p-13 j r+14 while TRUE/三次循环就把前一个数组搞定了5 do
4、repeat j j-16 until Ajx/后面小于主元7 repeat i i+1 8 until Aix/前面的大于主元9 if ij 10 then exchange Ai Aj11 else return j,划分的正确性,a.下标i和j不会指向数组A中区间p.r以外的元素。b.当PARTITION结束时，下标j不等于r。c.当PARTITION结束时，Ap.j中的每个元素都小于等于Aj+1.r中的每个元素。,性能分析,最坏情况划分：T(n)=T(n-1)+(n),最佳情况划分：T(n)=2T(n/2)+(n)=(nlgn),常数比例划分：T(n)=T(an)+T(1-a)n)+(
5、n)=(nlgn),平均情况划分：直觉：(nlgn)差的划分可以吸收到好的划分中。,三、快速排序的随机化版本,1.随机化版本的提出 2.在快速排序中使用随机选择策略 在快速排序算法的每一步中，当数组还没有被划分时，可将元素Ap与Ap.r中随机选出的一个元素交换后再执行PARTITION。3.使用随机化版本的优点,随机化版本的算法,RANDOMIZED-PARTITION1 i RANDOM(p,r)2 exchange Ap Ai3 return PARTITION(p,q,r)RANDOMIZED-QUICKSORT(A,p,r)1 if pr2 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),最坏情况分析,平均情况分析两个假设：（1）假设所有输入数据均不同；（2）假定每个排列出现是等概率的；,关于划分过程的分析关于平均情况性态的一个递归式解递归式上述和式的紧确界,关于划分过程的分析,关于平均情况性态的一个递归式,解递归式,上述和式的紧确界,The End,Thank you!,
