,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,10,章 排序,一、基本概念,排序,：,将文件中的记录按照,关键字值,递增或递减的顺序排列起来。,排序的稳定与不稳定,：若关键字相同的记录在排序后先后顺序仍然不变，则称所用的排序方法是稳定的，否则就是不稳定的。,内部排序,：全部在内存中进行的排序,外部排序,：排序中需使用内存与外存,内部排序：,插入排序，交换排序，选择排序，归并排序，基数排序等。,第10章 排序,1,内部排序与存储结构：,（,1,）一维数组作为存储结构：对记录进行物理重排；,（,2,）以链表作为存储结构：无须移动记录，仅需修改指针即可；,（,3,）建立索引表辅助排序,排序算法的评价标准：,（,1,）时间；（,2,）执行算法所需的附加空间；（,3,）算法复杂度。,主要是时间代价：,算法的比较次数和移动次数。,注：,简单的排序方法，时间复杂度,O(n,2,);,先进的排序方法，时间复杂度,O(nlogn),；基数排序，时间复杂度,O(d,n),。,内部排序与存储结构：,2,以数组作为文件的存储结构,#define MAXSIZE 100,typedef struct,KeyType key;,InfoType otherinfo;,RecType,;,typedef struct,RecType rMAXSIZE+1;/r0,闲置或作为哨兵单元,int length;,SqList,;,如：以某课程考试成绩为关键字的排序,以数组作为文件的存储结构,3,二、,插入排序,(Insertion Sort),定义：,将待排序记录分为有序区和无序区，每次将无序区中的第一个记录按其关键字值的大小插入到有序区中的适当位置，直到无序区记录全部插入为止。,1,直接插入排序,方法,：,在插入第,i,个记录时，,R,1,R,2,，,R,i-1,已排好序，将关键字,k,i,依次与关键字,k,i-1,k,i-2,k,1,进行比较，从而找到应该插入的位置，然后将记录,R,i,插入。,二、插入排序(Insertion Sort),4,对,R1Rn,进行排序，,R0,为监视哨,47 33 61 82 72 11 25 47,47,33 61 82 72 11 25 47,33,33 47,61 82 72 11 25 47 /3347,33,33 47 61,82 72 11 25 47,33,33 47 61 82,72 11 25 47,72,33 47 61 72 82,11 25 47,11,33 47 61 72,82,82,25 47 /1182,11,33 47 61,72,72,82,25 47 /1172,11,33 47,61,61,72 82,25 47 /1161,11,33,47,47,61 72 82,25 47 /1147,11,33,33,47 61 72 82,25 47 /1133,11,11 33 47 61 72 82,25 47,/,结束,11,的插入排序,25,11 25 33 47 61 72 82,47 /,47,11 25 33 47 47 61 72 82,中间过程,对R1Rn进行排序，R0为监视哨 ,5,算法：,void InsertSort(SqList&L),for(i=2;i=L.length;i+),if(L.ri.keyL.ri-1.key,),/,需将,L.ri,插入有序子表,L.r0=L.ri;,L.ri=L.ri-1;,for(j=i-2;,L.r0.key,L.rj.key;j-),L.rj+1=L.rj;/,记录后移,L.rj+1=L.r0;/,插入到正确位置,时间复杂度,O(n2),，稳定,算法：时间复杂度O(n2)，稳定,6,2,、,希尔排序,（,Shell,s method,）,“,缩小增量排序,”,(Diminishing Increment Sort),基本思想,：,先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录,“,基本有序,”,时，再对全体记录进行一次直接插入排序。,步骤,：,对整个待排记录序列，按间隔,d1,分组，组内排序,取,d2 0,）、,R,i+d*m,(i+d*m=n),同组,记录分组：,9,void,ShellInsert,(SqList&L,int dk),for(i=dk+1;i=L.length;i+),if(L.ri.key0,j-=dk),L.rj+dk=L.rj;/,记录后移,L.rj+dk=L.r0;/,插入到正确位置,void,ShellSort,(SqList&L,int,d,int t),/d,为增量序列数组，,t,为增量数,for(k=0;k1,47,33,61 82 72,11,若中间数介于,47,和,11,之间，必然减少逆转数,不稳定,当d=1时，逆转数=0不稳定,12,三、,选择排序,（,Selection Sort,）,基本思想,：,每一趟在待排序的记录中选出关键字最小的记录，依次放在已排序的记录序列的最后，直至全部记录排完为止。,三、选择排序（Selection Sort）,13,1.,简单选择排序,第一趟排序,：在无序区,R1Rn,中选出关键字最小的记录，将它与,R1,交换；,第二趟排序,：在无序区,R2Rn,中选出关键字最小的记录，将它与,R2,交换；,第,i,趟排序,：,R1Ri-1,已是有序区，在当前无序区,RiRn,中选出关键字最小的记录,Rk,，将它与,Ri,交换；,进行,n-1,趟排序后，整个文件就是递增有序的。,1.简单选择排序,14,49 38 65 97 76,13,27 49,13,38 65 97 76 49,27,49,13 27,65 97 76 49,38,49,13 27 38,97 76,49,65 49,13 27 38 49,76 97 65,49,13 27 38 49 49,97,65,76,13 27 38 49 49 65,97,76,13 27 38 49 49 65 76,97,13 27 38 49 49 65 76 97,49 38 65 97 76 13 27 4,15,算法流程：,1 for i=1 to n-1,j=i,for k=i+1 to n,if(RjRk)then j=k,end(k),if(ji)then ri,与,rj,互换,End(i),return,算法流程：,16,void,SelectSort(SqList&L),int i,j,k;RecType temp;,for(i=1;iL.length;i+),j=i;,for(k=i+1;kL.rk.key)j=k;,if(j i),temp=L.ri;,L.ri=L.rj;,L.rj=temp;,时间复杂度,O(n2),，稳定,void SelectSort(SqList&L)时间复,17,2.,堆排序,堆：,n,个元素的序列,k,1,k,2,k,n,，当且仅当满足以下关系时，称之为堆。,时间复杂度,O(nlogn),，不稳定,2.堆排序堆：n个元素的序列k1,k2,kn，当且,18,把堆看作一棵完全二叉树，所有非终端结点的值均不大于（或不少于）其左右孩子结点的值。,堆顶元素是堆序列的最小值（最大值）,把堆看作一棵完全二叉树，所有非终端结点的值均不大于（或不少于,19,堆排序,：输出堆顶最小值（最大值）后，使得剩余的元素序列重又建成一个堆，得到次小值（次大值）。如此反复执行得到一个有序序列的过程。,堆排序步骤：,1.,从无序序列构建初始堆,2.,反复筛选输出有序序列,第,1,步其实也是一个反复筛选的过程，因此筛选是堆排序的关键,堆排序：输出堆顶最小值（最大值）后，使得剩余的元素序列重又建,20,筛选过程,筛选过程,21,构建初始堆,构建初始堆,22,四、,交换排序,基本思想,：,两两比较待排序记录的关键字，发现两个记录逆序时即进行交换，直至没有逆序的记录为止。,四、交换排序,23,1,起泡排序,（,Bubble method,）,基本思想,：,通过对相邻关键字的比较和交换，使全部记录排列有序。,过程,：,每两个相邻的关键字进行比较，若为逆序，则将两记录交换位置，反复进行这一操作。如此一趟排序后，可将关键字最大的记录安排在最后一个记录的位置上，然后对前,n-1,个记录重复同样操作，再将次小关键字安排再倒数第二个记录的位置上。重复进行，直至某一趟没有记录交换完成排序。,1 起泡排序（Bubble method）,24,47,33,61,82,72,11,25,47,33,47,61,72,11,25,47,82,33,47,61,11,25,47,72,82,33,47,11,25,47,61,72,82,33,11,25,47,47,61,72,82,11,25,33,47,47,61,72,82,11,25,33,47,47,61,72,82,11,25,33,47,47,61,72,82,11,25,33,47,47,61,72,82,设置指示变量，以判断每次扫描时是否有记录交换,473333333311111111设置指示变量，以判断每次,25,void,BubbleSort,(SqList&L),int i,j,flag;RecType temp;,for(i=L.length;i1;i-),flag=TRUE;,for(j=1;jL.rj+1.key),temp=L.rj+1;L.rj+1=L.rj;,L.rj=temp;,flag=FALSE;,if(flag)break;,时间复杂度,O(n2),，稳定,void BubbleSort(SqList&L)时间,26,2,快速排序,（,Quick Sort,）,基本思想,：,通过一趟排序将原有记录分成两部分，然后分别对这两部分进行排序以达到最后所有记录有序。即在当前无序子区,R1Rh,中任取一个记录作为比较的基准，用此基准将当前无序区划分为左右两个较小的无序子区：,R1Ri-1,和,Ri+1Rh,，左边无序子区记录关键字均小于或等于基准关键字，右边则大于或等于基准关键字。反复进行，直至无序子区记录已排好序为止。,2 快速排序（Quick Sort）,27,对当前无序子区,R1Rh,进行划分的方法：,设置两个指示器,i,和,j,，它们的初值分别为：,i=1,j=h,。设基准,temp,为无序子区中的第一个记录,Ri(,即,R1),。将,j,自,h,起向左扫描，直至找到第一个关键字小于,temp.key,的记录,Rj,，将,Rj,移至,i,所指的位置上；然后，令,i,自,i+1,起向右扫描，直至找到第一个关键字大于,temp.key,的记录,Ri,，将,Ri,移至,j,所指的位置上；接着令,j,自,j-1,起向左扫描，如此交替改变扫描方向，从两端各自往中间靠拢，直至,i=j,时，,i,便是基准,x,的最终位置，将,x,放在此位置上就完成了一次划分。,O(nlogn),，不稳定,对当前无序子区R1Rh进行划分的方法：,28,49,38 65 97 76 13 27 49,i,j,49,38 65 97 76 13 27 49,i,j,27 38 65 97 76 13,49,49,i,j,27 38 65 97 76 13,49,49,i,j,27 38,49,97 76 13 65 49,i,j,49 38 65 97 76 13 27 4,29,49,38 65 97 76 13 27 49,i,j,49,38 65 97 76 13 27 49,i,j,27 38 65 97 76 13,49,i,j,27 38 65 97 76 13 49,i,j,27 38 97 76 13 65 49,i,j,49 38 65 97 76 13 27 4,30,