算法设计与分析7快速排序.pptx

算法设计与分析算法设计与分析谭守标谭守标安徽大学 电子学院2007.9第六章第六章 快速排序快速排序n快速排序算法快速排序算法n快速排序的随机化版本快速排序的随机化版本n程序演示及说明程序演示及说明n算法性能分析（三种情况）算法性能分析（三种情况）问题：问题：n1 1、什么是分治法？、什么是分治法？n2 2、什么是排序？、什么是排序？n3 3、用分治法解决排序问题的思想是什么、用分治法解决排序问题的思想是什么？n1.1.算法的提出：由算法的提出：由C.A.R.HoareC.A.R.Hoare提出。提出。n2.2.定义：快速排序定义：快速排序(quick sort)(quick sort)又称分划交又称分划交换排序。换排序。一、快速排序算法的基本概念一、快速排序算法的基本概念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+1.rAq+1.r进行排序。进行排序。nc.c.合并：快速排序无需合并操作。合并：快速排序无需合并操作。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)算法描述算法描述二、快速排序的分解、解决过程二、快速排序的分解、解决过程n1.1.分解：调用分解：调用PARTITIONPARTITION对数组对数组Ap.rApr进行划分。进行划分。分解方法：在待排序的数组分解方法：在待排序的数组Ap.rAp.r中选择一个元素作为中选择一个元素作为分划元素分划元素，也称为，也称为主元主元(最简单的做法是选择数组的第一个最简单的做法是选择数组的第一个元素为主元元素为主元)。经过一趟划分操作将数组重新排列，将小于经过一趟划分操作将数组重新排列，将小于主元的元素放在原数组的底部区域，把大于主元的元素放主元的元素放在原数组的底部区域，把大于主元的元素放在原数组的顶部区域。在原数组的顶部区域。示意图：示意图：主元主元 PARTITIONPARTITION75641233底部区域底部区域顶部区域顶部区域73146235n2.2解决：通过递归调用快速排序对子数组解决：通过递归调用快速排序对子数组Ap.qAp.q和和Aq+1.rAq+1.r排序，直到划分得到的子数排序，直到划分得到的子数组中只有一个元素时，递归调用结束。组中只有一个元素时，递归调用结束。n3.3.合并：快速排序经过一趟划分操作将数组分合并：快速排序经过一趟划分操作将数组分解成两个子数组，且位于底部区域的元素均不解成两个子数组，且位于底部区域的元素均不大于主元，位于顶部区域的元素均不小于主元，大于主元，位于顶部区域的元素均不小于主元，所以，一旦两个子数组已经完成分别排序，整所以，一旦两个子数组已经完成分别排序，整个数组自然成为有序序列。个数组自然成为有序序列。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一次划分结束一次划分结束主元主元returnreturn7314623573146235751462337514623375641233nPARTITION(A,p,r)PARTITION(A,p,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 Ai Ajn11 else return j11 else return j划分的正确性划分的正确性 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中的每个元素。中的每个元素。性能分析性能分析 n最坏情况划分：最坏情况划分：T(n)=T(n-1)+T(n)=T(n-1)+(n)(n)n最佳情况划分：最佳情况划分：T(n)=2T(n/2)+T(n)=2T(n/2)+(n)=(n)=(nlgn)(nlgn)n常数比例划分：常数比例划分：T(n)=T(an)+T(1-a)n)+T(n)=T(an)+T(1-a)n)+(n)=(n)=(nlgn)(nlgn)n平均情况划分：平均情况划分：直觉：直觉：(nlgn)(nlgn)差的划分可以吸收到好的划分中。差的划分可以吸收到好的划分中。三、快速排序的随机化版本三、快速排序的随机化版本n 1.1.随机化版本的提出随机化版本的提出n 2.2.在快速排序中使用随机选择策略在快速排序中使用随机选择策略n 在快速排序算法的每一步中，当数组在快速排序算法的每一步中，当数组还没有被划分时，可将元素还没有被划分时，可将元素ApAp与与Ap.rAp.r中随机选出的一个元素交换后再执行中随机选出的一个元素交换后再执行PARTITIONPARTITION。n 3.3.使用随机化版本的优点使用随机化版本的优点随机化版本的算法随机化版本的算法nRANDOMIZED-PARTITIONRANDOMIZED-PARTITIONn1 i RANDOM(p,r)1 i RANDOM(p,r)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-QUICKSORT(A,q+1,r)4 RANDOMIZED-QUICKSORT(A,q+1,r)四、快速排序分析四、快速排序分析(n-1)=n-2(n-1)n最坏情况分析最坏情况分析n平均情况分析平均情况分析两个假设：两个假设：（1 1）假设所有输入数据均不同；）假设所有输入数据均不同；（2 2）假定每个排列出现是等概率的；）假定每个排列出现是等概率的；n关于划分过程的分析关于划分过程的分析n关于平均情况性态的一个递归式关于平均情况性态的一个递归式n解递归式解递归式n上述和式的紧确界上述和式的紧确界关于划分过程的分析关于划分过程的分析关于平均情况性态的一个递归式关于平均情况性态的一个递归式解递归式解递归式上述和式的紧确界上述和式的紧确界The EndThe EndnThank you!Thank you!