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

算法设计与分析7快速排序,1,算法设计与分析,2007.9,算法设计与分析7快速排序,2,第六章 快速排序,快速排序算法 快速排序的随机化版本 程序演示及说明 算法性能分析（三种情况）,算法设计与分析7快速排序,3,问题：,1、什么是分治法？ 2、什么是排序？ 3、用分治法解决排序问题的思想是什么？,算法设计与分析7快速排序,4,1.算法的提出：由C.A.R.Hoare提出 2.定义：快速排序(quick sort)又称分划交换排序一、快速排序算法的基本概念,算法设计与分析7快速排序,5,3.其解决排序问题的基本思路：使用分治法 基本步骤： a.分解：数组Ap.r被划分为两个非空子数组Ap.q和Aq+1.r,使得Ap.q的每一个元素都小于等于Aq+1.r的元素 b.解决：通过递归调用快速排序对子数组Ap.q和Aq+1.r进行排序 c.合并：快速排序无需合并操作算法设计与分析7快速排序,6,快速排序算法: 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),算法描述,算法设计与分析7快速排序,7,二、快速排序的分解、解决过程,1. 分解：调用PARTITION对数组Ap.r进行划分。

分解方法：在待排序的数组Ap.r中选择一个元素作为分划元素，也称为主元(最简单的做法是选择数组的第一个元素为主元) 经过一趟划分操作将数组重新排列，将小于主元的元素放在原数组的底部区域，把大于主元的元素放在原数组的顶部区域 示意图： 主元 PARTITION,底部区域,顶部区域,算法设计与分析7快速排序,8,2.解决：通过递归调用快速排序对子数组Ap.q和Aq+1.r排序，直到划分得到的子数组中只有一个元素时，递归调用结束 3.合并：快速排序经过一趟划分操作将数组分解成两个子数组，且位于底部区域的元素均不大于主元，位于顶部区域的元素均不小于主元，所以，一旦两个子数组已经完成分别排序，整个数组自然成为有序序列算法设计与分析7快速排序,9,PARTITION实例：,i,j,i,i,j,j,i,j,j,i,(a),(b),(c),(d),(e),Ap.r,Ap.q,Aq+1.r,一次划分结束,主元,return,算法设计与分析7快速排序,10,PARTITION(A,p,r) 1 x Ap 2 i p-1 3 j r+1 4 while TRUE /三次循环就把前一个数组搞定了 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,算法设计与分析7快速排序,11,划分的正确性,a.下标i和j不会指向数组A中区间p.r以外的元素。

b.当PARTITION结束时，下标j不等于r c.当PARTITION结束时，Ap.j中的每个元素都小于等于Aj+1.r中的每个元素算法设计与分析7快速排序,12,性能分析,最坏情况划分： T(n)=T(n-1)+(n),算法设计与分析7快速排序,13,最佳情况划分： T(n)=2T(n/2)+(n)=(nlgn),算法设计与分析7快速排序,14,常数比例划分： T(n)=T(an)+T(1-a)n)+(n)=(nlgn),算法设计与分析7快速排序,15,平均情况划分： 直觉：(nlgn) 差的划分可以吸收到好的划分中算法设计与分析7快速排序,16,三、快速排序的随机化版本,1. 随机化版本的提出 2.在快速排序中使用随机选择策略 在快速排序算法的每一步中，当数组还没有被划分时，可将元素Ap与Ap.r中随机选出的一个元素交换后再执行PARTITION 3.使用随机化版本的优点,算法设计与分析7快速排序,17,随机化版本的算法,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),算法设计与分析7快速排序,18,四、快速排序分析,(n-1) =,n -2(n-1),最坏情况分析,算法设计与分析7快速排序,19,算法设计与分析7快速排序,20,平均情况分析 两个假设： （1）假设所有输入数据均不同； （2）假定每个排列出现是等概率的；,算法设计与分析7快速排序,21,关于划分过程的分析 关于平均情况性态的一个递归式 解递归式 上述和式的紧确界,算法设计与分析7快速排序,22,关于划分过程的分析,算法设计与分析7快速排序,23,算法设计与分析7快速排序,24,关于平均情况性态的一个递归式,算法设计与分析7快速排序,25,解递归式,算法设计与分析7快速排序,26,算法设计与分析7快速排序,27,上述和式的紧确界,算法设计与分析7快速排序,28,The End,Thank you!,。