2霍尔快速排序图示

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,枢轴,49,49,38 65 97 76 13 27,49,比右,2.霍尔快速排序图示,27 38 65 97 76 13,27,49,比左,j,j,j,i,i,i,27 38,65,97 76 13 65,49,比右,第一趟：,枢轴,49,27 38 13 97 76,13,65,49,比左,2.霍尔快速排序图示,第一趟结果：,27 38 13 ,49,76 97 65,49,27 38 13,97,76 97 65,49,比右,i,j,j,i,小于,49,大于等于,49,第一趟：,对于左子表，,枢轴是,27,27,38 13 先比较右端,13 38,13,比较左端,13,38,38 指针相碰,13 27 38 本趟结束,第一趟结果,27 38 13,49,76 97 65,49,j,i,i,i,j,j,右子表枢轴,76,97 65,49,49,97 65,49,49,97,65 97,49,65,65,97,指针相碰枢轴到位,49,65,76,97,新的结果 13 27 38 49,76 97 65,49,j,j,j,j,i,i,i,i,76,本趟枢轴是,49,49,65,49,65,新结果,13 27 38 49,49,65,76,97,结果 13 27 38 49,49,65 76 97,i,i,j,j,3,.,算法实现：,（1）,将一个表分成两个子表的过程；,返回值是,枢轴,i,int hoarepass,(,listtp,r,int,low,int,high),/*low,、,high,分别,是表头、尾,指针 */,；,return(i);,/*,i,为,枢轴位置*/,/*,hoarepass,*/,左子表,右子表：,rs.ri-1,rs,ri+1.rt,int hoarepass,(,listtp,r,int,low,int,high),/*low,、,high,分别,是表头、尾,指针 */,x,=rlow;i=low;j=high;,while(ij),while (i=,x.key,)j-;,ri=rj;,/*,较小值移到左端*/,while (ij&ri.key,x.key,)i+;,rj=ri;,/*,较大,值向右移*/,ri=,x,;,/*,i,为,枢轴位置*/,return(i);,/*,hoarepass,*/,（2）快速排序,主体算法,void,hoare,_sort(,listtp,r),/*,sa,是,一个栈,int,sa,MAX2;,存放右子表头、尾位置 */,top=0;low=1;high=n;,bool,=0;,do,while(lowhigh),k=,hoarepass,(r,low,high);,/*k,为,枢轴位置*/,top+;,sa,top0=k+1;,/*,右,表头*/,sa,top1,:=high,;,/*,右,表尾*/,/*,左,表头不变为,low*/,high=k-1;,/*,左表,尾*/,;,if(top=0),bool,=1;,else low=,sa,top0;high=,sa,top1;top-;,while(,bool,=0);,/*,hoare,_sort*/,递归算法见,P276,算法10.7,4.算法分析:,（1）,所用辅助空间:一个记录+一个栈，,特殊情况下，栈最大深度为,n。,一般情况下:,log,2,n,为栈的深。,（2）比较次数：,一般情况下:,T(n)=0(n*log,2,n),其中,log,2,n,代表,栈的深,，,n,反应每个子表比较次数的数量级。,最坏情况,（,原表有序时）：0(,n,2,),注意：枢轴位置选法不唯一。,数据结构课件,内部排序,第二讲,2004年12月,上一讲内容回顾,插入,排序,直接插入排序,稳定,T(n)=O(n,2,),交换排序,起泡排序,稳定,T(n)=O(n,2,),原表有序时,T(n)=O(n),快速排序,不稳定,O(n.log,2,n),原表有序时,T(n)=O(n,2,),本讲内容,选择,排序,简单选择排序,稳定,T(n)=O(n,2,),堆排序,不稳定,T,(n)=O(n.log,2,n),归并,排序,两路归并排序,稳定,T,(n)=O(n.log,2,n),9,.,4,选择排序,一、简单选择排序：,思路：,组织外循环（趟）,i,=1,n-1,每趟：从,ri,ri+1,.,rn,选关键字最小值的记录放,ri,；,算法分析,时间复杂度：,T(n)=O(n,2,),排序稳定,一、简单选择排序算法,void,smp,_,selecpsort,(,listtp,r),for(,i=,1;i=n-1;i+),k=,i;,/*,记下较小值的下标*/,for(j=,i+1,;j=n;j+),if(rj.keyrk.key)k=j;,if (k!=i),x=rk;rk=,ri;ri,=x;,/*,smp,_,selecpsort,*/,二、,堆排序,：,1.,堆的,概念：,n,个元素序列,k,1,k,2,.,k,n,当且仅当满足:,k,i,=k,2i,(i=1,2,.,n/2),k,i,=k,2i+1,关键字：12 19 65 38 27 73,下标,i,：1 2 3 4 5 6,r,i,r,2i,r,2i+1,把它对应的一维数组如果看成,完全二叉树,，,结点编号的关系与,性质5,相符合。,则,r,2i,是,r,i,的,左,孩子;,r,2i+1,是,r,i,的,右,孩子;,“树”中非终端结点的值均不大于左右孩子的值,关键字：12 19 65 38 27 73,下标,i,：1 2 3 4 5 6,12,19,65,38,27,例如:,是堆（小顶）,73,再如,关键字：12 19 65 38 27 36,下标,i,：1 2 3 4 5 6,12,19,65,38,27,73,是堆,36,不,12 19 27 11 20 12 19 65 38 27 73,12 12,19 27 19 65,11,20 38 27 73,堆的判断练习,非 堆 是 堆,2.堆排序：,(1),初建堆,将原始数据序列，,调整成堆,关系；,堆顶元素是,最小值（小顶堆）,(,2)不断输出堆顶元素；,将堆尾元素移至堆顶，,再,调整成堆,。,