《数据结构》课件第10章 内部排序_2

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,10,章 内部排序,学习要点,:,深刻理解排序的定义和各种排序方法的特点,了解各种方法的排序过程及其依据的原则,掌握各种排序方法的时间复杂度的分析方法,理解排序方法“稳定”或“不稳定”的含义,重点掌握,希尔,排序、,快速,排序、,堆,排序和,归并,排序等高效方法,10.4,选择排序,基本原理,：将待排序的记录分为,已排序,(,初始为空,),和,未排序,两组，依次将未排序的记录中值,最小,/,大的插入已排序的组中,。,简单选择排序,堆排序,10.4.1,简单选择排序,基本操作过程：,假设排序过程中，待排记录序列的状态为：,有序序列,R1.i-1,无序序列,Ri.n,第,i,趟,简单选择排序,从中选出,关键字最小,的记录,有序序列,R1.i,无序序列,Ri+1.n,n-i+1,算法描述：,void,SelectSort,(Elem R,int,n ) ,/,对记录序列,R1.n,作简单选择排序,for (i=1; in; +i) ,/,选择第,i,小的记录，并交换到位,j =,SelectMinKey,(R, i);,/,在,R,i,.,n,中选择关键字最小的记录，,用,j,记录,该位置,if (i!=j),RiRj,;,/,与第,i,个记录交换, /,SelectSort,例：,初始：, 49 38 65 97 76 13 27 ,j,k,k,k,k,k,k,j,j,i=1,13,49,一趟后：,13, 38 65 97 76 49 27 ,i=2,j,j,k,k,k,k,k,27,38,二趟：,13,27,65 97 76 49 38 ,三趟：,13,27,38,97 76 49 65 ,四趟：,13,27,38,49,76 97 65 ,五趟：,13,27,38,49,65,97 76 ,六趟：,13,27,38,49,65,76,97 ,排序结束：,13,27,38,49,65,76,97,1,2,3,4,5,6,7,时间性能分析：,对,n,个记录进行简单选择排序，所需进行的,关键字间的比较次数,总计为：,移动记录的次数：,最小值为,0,最大值为,3(,n,-1) (,每次交换移动,3,次,),事实上，可以利用前,n,-1,次比较所得信息减少以后各趟选择排序中所用的比较次数。,树形选择排序,(,详见教材,P278,P279),10.4.2,堆排序,堆排序,只需,要,一个记录大小,的辅助空间。,堆的定义,：,n,个,元素的序列 ,k,1,，,k,2,，,，,k,n,，,当且仅当满足以下关系时，称之为,堆,。,k,i,=,k,2,i,k,i,=,k,2,i,+1,(,i,= 1,2, ,n,/2,),例如：,序列, 96, 83, 27, 11, 9,大顶堆；, 12, 36, 24, 85, 47, 30, 53, 91,小顶堆,或,96,9,11,83,27,2,3,1,4,5,12,47,85,91,36,24,53,30,6,2,7,3,1,8,4,5,完全二叉树的非终端结点的值均不大于,(,或不小于,),其左、右孩子结点的值。,小顶堆,大顶堆,序列：,12, 36, 27, 65, 40,14, 98, 81, 73, 55, 49,堆排序即是利用,堆的特性,对记录序列进行排序的一种排序方法。,在排序过程中，将,R1,到,Rn,看成是一个,完全二叉树顺序存储结构,，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小,/,大的记录。,12,36,27,65,49,81,73,55,40,14,98,不是堆,14,例如：,堆排序分为两个步骤：,根据初始输入，形成初始堆。,通过一系列的,记录交换,和,重新调整,进行排序。,建大顶堆,即,k,i,=k,2i,且,k,i,=k,2i+1,98,81, 49, 73, 36, 27, 40, 55, 64, 12 ,12,81, 49, 73, 36, 27, 40, 55, 64 , 98,交换,98,和,12,重新调整为大顶堆,81,73, 49, 64, 36, 27, 40, 55, 12 , 98, 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 ,经过筛选,建堆,筛选,定义堆类型为：,typedef,SqList,HeapType,; /,堆采用顺序表表示,如何“,筛选,”？,“筛选”指的是，对一棵,左,/,右子树均为堆,的完全二叉树，,“调整”根结点,使整个二叉树也成为一个堆。,堆,堆,筛选,例如：,98,81,49,73,55,64,12,36,27,40,是一个大顶堆,12,但，在,98,和堆中最后一个元素,12,进行互换之后，它,就,不是,堆了。,98,12,81,73,64,12,98,比较,比较,因此，需要对它进行,“,筛选,”,。,算法描述：,void,HeapAdjust,(,RcdType,&R,int,s,int,m), /,已知,Rs.m,中记录的关键字除,Rs,之外均,/,满足堆的特征，本函数,自上而下,调整,Rs,的,/,关键字，使,Rs.m,也成为一个大顶堆,rc,=,Rs,; /,暂存,Rs,for ( j=2*s; j=m; j*=2 ) / j,初值指向左孩子,自上而下的筛选过程,;,Rs, =,rc,; /,将调整前的堆顶记录插入到,s,位置, /,HeapAdjust,if ( jm &,Rj.key,=,Rj.key,) break;,/,再作“根”和“子树根”之间的比较，,/,若“,=”,成立，则说明已找到,rc,的插,/,入位置,s,，不需要继续往下调整,Rs, =,Rj,; s = j;,/,否则记录上移，尚需继续往下调整,如何“建堆”？,建堆是一个,从下往上,进行“,筛选,”的过程。,例如：排序之前的关键字序列对应的完全二叉树如下,40,55,49,73,81,64,36,12,27,98,12,36,81,73,49,98,81,73,55,现在，左,/,右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个,“,堆,”,即可。,98,49,40,64,36,12,27,从最后一个非终端结点，即,第,n/2,个元素开始“筛选”！,例如：关键字序列为,42,，,13,，,91,，,23,，,24,，,16,，,05,，,88,，用堆排序进行,降序,排列。,分析：,首先，依据关键字序列构造完全二叉树,(,采用顺序存储结构,),；,然后，进行建堆和筛选，以便实现推排序。,42,13,91,23,24,16,05,88,42,13,91,23,24,16,05,88,n=8,，故从第,4,个,结点开始调整,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,不调整,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,42,88,91,23,24,16,05,13,42,88,91,23,24,16,05,13,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,建成的堆,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,（,a,）,初始堆,R1,到,R8,13,88,42,23,24,16,05,91,13,88,42,23,24,16,05,91,（,b,）,第一趟排序之后,（,c,）,重建的堆,R1,到,R7,88,24,42,23,13,16,05,91,88,24,42,23,13,16,05,91,05,24,42,23,13,16,88,91,05,24,42,23,13,16,88,91,（,d,）,第二趟排序之后,（,e,）,重建的堆,R1,到,R6,42,24,16,23,13,05,88,91,42,24,16,23,13,05,88,91,（,f,）,第三趟排序之后,05,24,16,23,13,42,88,91,05,24,16,23,13,42,88,91,（,g,）,重建的堆,R1,到,R5,24,23,16,05,13,42,88,91,24,23,16,05,13,42,88,91,（,h,）,第四趟排序之后,13,23,16,05,24,42,88,91,13,23,16,05,24,42,88,91,（,i,）,重建的堆,R1,到,R4,23,13,16,05,24,42,88,91,23,13,16,05,24,42,88,91,（,j,）,第五趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,（,k,）,重建的堆,R1,到,R3,16,13,05,23,24,42,88,91,16,13,05,23,24,42,88,91,（,l,）,第六趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,（,m,）,重建的堆,R1,到,R2,13,05,16,23,24,42,88,91,13,05,16,23,24,42,88,91,（,n,）,第七趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,堆排序的时间复杂度分析：,对深度为,k,的堆，“筛选”所需进行的关键字比较的次数至多为,2(,k,-1),；,对,n,个关键字，建成深度为,h,(=,log,2,n,+1),的堆，,所需进行的关键字比较的次数至多,4,n,；,调整“堆顶”,n-,1,次，总共进行的关键字比较的次数不超过：,2 (,log,2,(n,-1,),+,log,2,(n,-2,),+ +,log,2,2),2,n,(,log,2,n,),因此，堆排序的时间复杂度为,O(nlogn,),。,空间复杂性为,O,(1),堆排序是,不稳定,的排序方法。,课后作业,P63,：,10.12,(1),和,(2),10.5,归并排序,归并排序的过程基于下列,基本思想,进行：,将两个或两个以上的,有序,子序列,合并,为一个有序序列。,在内部排序中，通常采用的是,2-,路归并,排序。即：,将两个位置相邻的记录有序子序列,归并为一个记录的有序序列,这个操作对顺序表而言，是轻而易举的。,有序子序列,R,l,.,m,有序子序列,R,m,+1.,n,有 序 序 列,R,l,.,n,void Merge (,RcdType,SR,RcdType,&TR,int,i,int,m,int,n),/,将,有序的,记录序列,SRi.m,和,SRm+1.n,/,归并为有序的记录序列,TRi.n,for (j=m+1, k=i; i=m +k), /,将,SR,中记录由小到大地并入,TR,if (,SRi.key,=,SRj.key,),TRk, =,SRi,+;,else,TRk, =,SRj,+;,if (i=m),TRk.n, =,SRi.m,;,/,将剩余的,SRi.m,复制到,TR,if (j=n),TRk.n, =,SRj.n,;,/,将剩余的,SRj.n,复制到,TR, / Merge,归并排序的算法：,如果记录无序序列,Rs.t,的两部分,R,s,.,(,s+t,)/2,和,R,(,s+t,)/2,+1.,t,分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。,由此，应该先分别对这两部分,(R,s,.,(,s+t,)/2,和,R,(,s+t,)/2,+1.,t,),进行,2-,路,归并排序。,例如：,52, 23, 80, 36, 68, 14 (s=1, t=6), 52, 23, 80,36, 68, 14, 52, 23,80, 52, 23, 52,23, 52, 80,36, 68,14,36,68,36, 68,14, 36, 68, 14, 23, 36, 52, 68, 80 ,23,10.6,基数排序,基数排序是一种借助,“,多关键字排序,”的思想,来实现“单关键字排序”的内部排序算法。,10.6.1,多关键字的排序,n,个记录的序列, R,1, R,2, ,，,R,n,对关键字,(K,i,0, K,i,1,K,i,d-1,),有序是指：,对于序列中任意两个记录,R,i,和,R,j,(1i,jn,),都满足下列,(,词典,),有序关系：,(K,i,0, K,i,1, ,K,i,d-1,) (K,j,0, K,j,1, ,K,j,d-1,),其中,:,K,0,被称为,“最主”位关键字；,K,d-1,被称为,“,最次”位关键字,两种方法：,先对最主位关键字,K,0,进行排序，将序列分成若干子序列，依次再对子序列对,K,1,进行排序，重复分割。,最高位优先法,从最次位关键字,K,d-1,起进行排序，然后对高一位的关键字进行排序，依次重复。,最低位优先法,基数排序：借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法。,10.7,各种排序方法的综合比较,时间性能：,平均的时间性能：,时间复杂度为,O,(,n,log,n,),：,快速排序、堆排序和归并排序,时间复杂度为,O,(,n,2,),：,直接插入排序、起泡排序和简单选择排序,时间复杂度为,O,(,n,),:,基数排序,当待排记录序列按关键字顺序有序时：,直接插入排序,和,起泡排序,能达到,O,(,n,),的时间复杂度,快速排序,的时间性能,蜕化为,O,(,n,2,),简单选择,排序、,堆,排序和,归并,排序的时间性能,不随,记录序列中关键字的分布而改变。,空间性能：指的是排序过程中所需的辅助空间大小。,所有的,简单排序方法,(,包括：直接插入、起泡和简单选择,),和,堆排序,的空间复杂度为,O,(1),；,快速排序,为,O,(log,n,),，,为递归程序执行过程中，栈所需的辅助空间；,归并排序,所需辅助空间最多，其空间复杂度为,O,(,n,);,链式基数排序,需附设队列首尾指针，则空间复杂度为,O,(,rd,),。,排序方法的稳定性能：,稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。,排序之前,: ,R,i,(K,) ,R,j,(K,) ,排序之后,: ,R,i,(K,),R,j,(K,) ,当对多关键字的记录序列进行,最低位优先,LSD,方法排序时，,必须,采用,稳定的,排序方法。,对于不稳定的排序方法，只要能举出一个实例说明即可。,例如：对,4, 3, 4, 2 ,进行快速排序，,得到, 2, 3, 4,4,快速排序、堆排序和希尔排序是,不稳定,的排序方法。,本章小结,基于“,关键字间的比较,”进行排序的方法可以按排序过程所依据的不同原则分为：,插入排序,交换排序,选择排序,归并排序,基数排序,