资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,4.6.2,快速排序,一,.,基本思想,任取待排序序列中的某个元素作为,基准,（一般取第一个元素），将待排序元素,分为左右两个子表,，左子表中元素的关键字值均小于或等于基准元素的关键字值，右子表中元素的关键字值均大于或等于基准元素的关键字值，然后分别对两个子表继续进行划分，直至每一个子表,只有一个元素或为空,为止。最后得到的便是有序序列。,怎样具体实现？,概括地说：,一次划分就是从表的两端,交替方向,地向中间进行扫描,将小的放到左边,大的放到右边,作为基准的元素放到中间。,快速排序一次划分过程,38,20 46,38,74 91 12,思考：怎样为,38,找位置，正确地实现表的一次划分？,快速排序一次划分过程,1,i,指向待划分区域最左端，,j,指向待划分区域最右端,;,2.,保存基准元素的值，,r0=,ri,;,3.,从右向左扫描,(,首先开始此方向的扫描,),j,从,右向左,移动，直到,rj.key,r0.key,或,i=j;,4.,若,rj.key,r0.key,或,i=j;,6.,若,ri.key,r0.key,，则,r,j,=,ri,j=j-1,，改变扫描方向,;,7.,重复,36,，直到,i,j,位置重合（即,i=j,），此位置即最终的划分位置；,8.,将基准元素放入,最终的划分位置，,ri,=r0,或,rj,=r0,为了减少数据的移动,将作为基准的元素暂存到,r0,中，最后再放入最终位置,2,r0=,ri,一次划分过程演示,i,38,20,46,38,74,91,12,j,0 1 2 3 4 5 6 7,1,i,指向待划分区域最左端（,low,）；,j,指向待划分区域最右端（,high,）；,38,low,high,一次划分过程演示,i,38,20,46,38,74,91,12,j,0 1 2 3 4 5 6 7,3.j,从右向左移动直到,rj.key,r0.key,或,i=j;,38,一次划分过程演示,i,38,20,46,38,74,91,12,j,0 1 2 3 4 5 6 7,4.,若,rj.key,r0.key,或,i=j;,38,一次划分过程演示,i,12,20,46,38,74,91,12,j,0 1 2 3 4 5 6 7,6.,若,ri.key,r0.key,，,则,rj,=,ai,，,j=j-1,，改变扫描方向,;,38,46,一次划分过程演示,i,12,20,46,38,74,91,46,0 1 2 3 4 5 6 7,38,38,令：,mid=j,，形成两个子表：,lowmid-1,和,mid+1high,一次划分过程结束,j,low,high,mid,3.j,从右向左移动直到,rj.key,r0.key,或,i=j;,i,j,位置重合,扫描结束,将基准元素放入最终确定的划分位置,(,i,j,重合处,),实现一次划分的算法：,int,Partition(list,r,int,i,int,j),r0=,ri,;,/*,暂存基准元素到,r0,中*,/,while(i,j),/*,从表的两端交替地向中间扫描*,/,while(i,=r0.key),j-;,if(i,j),ri,=,rj,;,i+;,while(i,j&ri.key,=r0.key),i+;,if(ij),rj,=,ri,;j-;,ri,=r0;/*,将基准元素放到其最终位置*,/,return i;,/*,返回基准元素所在的位置*,/,二,.,算法实现,递归算法分析,递归退出的条件：,数据表为空或数据表中只有一个元素。,即,:,lowhigh,。,大规模问题与小规模问题的关系：,对一个,lowhigh,区间的表的排序变成对,lowmid-1,和,mid+1high,两个子表的排序。,快速排序的递归过程,38,20 46,38,74 91 12,初始状态,12 20,38,38,74 91 46,第,1,次划分,分别快速排序,12,20,38,74 91 46,结束,46,74,91,结束,12,20 38,38,46 74 91,排序结果,递归算法,void,QSort(list,r,int,low,int,high),/*,对,rlow,到,rhigh,范围内的元素进行快速排序*,/,int,mid;,if(lowhigh),mid=,Partition(r,low,high,);,QSort(r,low,mid-1);,QSort(r,mid+1,high);,下面的快速排序算法实现将一个长度为,n,的线性表,r,上的所有元素按关键字升序排列。,void,Quick_Sort(list,r,int,n),QSort(r,1,n);,算法分析,4 3,3,稳定性,:,不稳定的,时间复杂度,:,(n,2,),最快的情况：,数据分布均匀,最慢的情况：,正序或逆序,O,（,nlog,2,n,）,时间复杂度：,i,j,3,4,4,先暂存在,r0,中,4,3,3,3,i,j,结果：,3,3 4,快速排序的递归树,38,12,38,91,20,74,46,1,2,3,4,深度越小效率越高,思考题,“,三者取中,”,的规则,“,三者取中,”,规则，即在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区间的第,1,个记录进行交换，此后的划分过程与上面所给的,Partition,算法完全相同。,开动脑筋,基准元素如何选取能提高快速排序的时间性能？,课后练习题,1,假如待排序的关键字序列为,1,，,2,，,3,，,4,，,5,，,6,，,7,，请问初始状态为什么时，快速排序效率最高？,2,给定一组关键字序列,19,，,26,，,92,，,87,，,11,，,43,，,87,，,21,，用快速排序方法进行升序排列，写出每趟排序后关键字的排列情况。,
展开阅读全文