算法设计与分析-7快速排序ppt课件

1、算法设计与分析算法设计与分析谭守标谭守标安徽大学安徽大学 电子学院电子学院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 so

2、rt)又称分划交又称分划交换排序。换排序。一、快速排序算法的根本概念一、快速排序算法的根本概念n3.3.其处理排序问题的根本思绪：运用分其处理排序问题的根本思绪：运用分治法。治法。n根本步骤：根本步骤：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.

3、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. 分解：调用PARTITION对数组Ap.r

4、进展划分。n 分解方法：在待排序的数组Ap.r中选择一个元素作为分划元素，也称为主元(最简单的做法是选择数组的第一个元素为主元)。 经过一趟划分操作将数组重新陈列，将小于主元的元素放在原数组的底部区域，把大于主元的元素放在原数组的顶部区域。n 表示图：n 主元 PARTITION75641233底部区域底部区域顶部区域顶部区域73146235n2.2.处理：经过递归调用快速排序对子数组处理：经过递归调用快速排序对子数组Ap.qAp.q和和Aq+1.rAq+1.r排序，直到划分得到的子数排序，直到划分得到的子数组中只需一个元素时，递归调用终了。组中只需一个元素时，递归调用终了。n3.3.合并：快

5、速排序经过一趟划分操作将数组分合并：快速排序经过一趟划分操作将数组分解成两个子数组，且位于底部区域的元素均不解成两个子数组，且位于底部区域的元素均不大于主元，位于顶部区域的元素均不小于主元，大于主元，位于顶部区域的元素均不小于主元，所以，一旦两个子数组曾经完成分别排序，整所以，一旦两个子数组曾经完成分别排序，整个数组自然成为有序序列。个数组自然成为有序序列。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一次划分终了一次

6、划分终了主元主元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

7、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中的

8、每个中的每个元素都小于等于元素都小于等于Aj+1.rAj+1.r中的每个元素。中的每个元素。性能分析性能分析 n最坏情况划分：最坏情况划分：nT(n)=T(n-1)+T(n)=T(n-1)+(n)(n)n最正确情况划分：最正确情况划分：nT(n)=2T(n/2)+T(n)=2T(n/2)+(n)=(n)=(nlgn)(nlgn)n常数比例划分：常数比例划分：nT(n)=T(an)+T(1-a)n)+T(n)=T(an)+T(1-a)n)+(n)=(n)=(nlgn)(nlgn)n平均情况划分：平均情况划分：n直觉：直觉：(nlgn)(nlgn)n差的划分可以吸收到好的划分中。差的划分可以吸收到

9、好的划分中。三、快速排序的随机化版本三、快速排序的随机化版本n 1. 1. 随机化版本的提出随机化版本的提出n 2. 2.在快速排序中运用随机选择战略在快速排序中运用随机选择战略n 在快速排序算法的每一步中，在快速排序算法的每一步中，当数组还没有被划分时，可将元素当数组还没有被划分时，可将元素ApAp与与Ap.rAp.r中随机选出的一个元中随机选出的一个元素交换后再执行素交换后再执行PARTITIONPARTITION。n 3. 3.运用随机化版本的优点运用随机化版本的优点随机化版本的算法随机化版本的算法nRANDOMIZED-PARTITIONRANDOMIZED-PARTITIONn1 i

10、 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平均情况分析平均情况分析n两个假设：两个假设：n1 1假设一切输入数据均不同；假设一切输入数据均不同；n2 2假定每个陈列出现是等概率的；假定每个陈列出现是等概率的；n关于划分过程的分析