第十章10排序.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第十章,排序,2,10.1,概述,10.2,插入排序,10.3,快速排序,10.4,堆排序,10.5,归并排序,10.6,各种排序方法的综合比较,3,10.1,概 述,一、排序的定义,二、内部排序和外部排序,三、内部排序方法的分类,4,1.,什么是排序？,将一组杂乱无章的,数据,按一定,规律,顺次排列起来2.,排序的目的是什么？,存放在数据表中,按关键字排序,便于查找！,一、排序的定义,5,排序是计算机内经常进行的一种操作，其目的是将一组,“无序”的记录序列调整为“有序”,的记录序列例如：,将下列关键字序列,52,49,80,36,14,58,61,23,97,75,调整为,14,23,36,49,52,58,61,75,80,97,6,一般情况下，,假设含,n,个记录的序列为,R,1,R,2,，,R,n,其相应的关键字序列为,K,1,K,2,，,K,n,这些关键字相互之间可以进行比较，即在,它们之间存在着这样一个关系：,K,p1,K,p2,K,pn,按此固有关系将上式记录序列重新排列为,R,p1,R,p2,，,R,pn,的,操作,称作,排序,。

7,排序码（,Sort Key,）,:,作为排序依据的记录中的一个属性它可以是任何一种可比的有序数据类型，它可以是记录的关键字，也可以是任何非关键字在此我们认为对任何一种记录都可找到一个取得它排序码的函数,Skey(,一个或多个关键字的组合,),8,排序算法的好坏如何衡量？,时间效率,排序速度（,比较次数,与,移动次数,）,空间效率,占内存辅助空间的大小,稳定性,A,和,B,的关键字相等，排序后,A,、,B,的先后次序保持不变，则称这种排序算法是稳定的9,若待排序记录都在内存中，称为内部排序；,若,整个排序过程,不需要访问外存,便能完成，则称此类排序问题,为,内部排序,；,若待排序记录一部分在内存，一部分在外存，则称为外部排序若参加排序的记录数量很大，整个序列的排序过程,不可能在内存中完成,，则称此类排序问题,为,外部排序,注：,外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多二、内部排序和外部排序,10,记录序列以,顺序表存储,Typedef struct,/,定义每个记录（数据元素）的结构,KeyType,key,;,/,关键字,InfoType otherinfo;,/,其它数据项,RedType,;,Typedef struct,/,定义顺序表的结构,RedType,r MAXSIZE+1;,/,存储顺序表的向量,/r0,一般作哨兵或缓冲区,int length;,/,顺序表的长度,SqList;,#define MAXSIZE 20,/,设记录不超过,20,个,typedef,int,KeyType;,/,设关键字为整型量（,int,型）,11,内部排序的过程是一个,逐步扩大,记录的,有序序列长度,的过程。

经过一趟排序,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,三、内部排序方法的分类,12,排序算法分类,规则不同,插入排序,交换排序,选择排序,归并排序,时间复杂度不同,简单排序,O(n,2,),先进排序,O(nlog,2,n,),13,内排序框架图,14,10.2,插 入 排 序,15,插入类,将无序子序列中的,一个或几个记录,“,插入,”,到有序序列中，从而增加记录的有序子序列的长度基本思想：,每步将一个待排序的对象，按其关键码大小，,插入到前面,已经排好序的一组对象,的,适当位置,上,，直到对象全部插入为止即边插入边排序，保证子序列中随时都是排好序的,16,有序序列,R1.i-1,Ri,无序序列,Ri.n,一趟直接插入排序的基本思想：,有序序列,R1.i,无序序列,Ri+1.n,17,实现“一趟插入排序”可分三步进行：,3,将,Ri,插入,(,复制,),到,Rj+1,的位置上2,将,Rj+1,.,i-1,中的所有,记录,均,后移,一个位置；,1,在,R1.i-1,中,查找,Ri,的插入位置，,R1.j.key,Ri.key,Rj+1.i-1.key,；,18,直接插入排序,（基于顺序查找）,不同的具体实现方法导致不同的算法描述,折半插入排序,（基于折半查找）,希尔排序,（基于逐趟缩小增量）,19,一、直接插入排序,直接插入排序的基本思想是：,把,n,个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有,n-1,个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

20,排序过程：整个排序过程为,n-1,趟插入，即先将序列中,第1个记录,看成是一个有序子序列，然后从,第2个记录,开始，,逐个,进行插入，直至整个序列有序,13,】,6,3,31,9,27,5,11,【,6,13,】,3,31,9,27,5,11,【,3,6,13,】,31,9,27,5,11,【,3,6,13,，,31,】,9,27,5,11,【,3,6,9,13,，,31,】,27,5,11,【,3,6,9,13,，,27,31,】,5,11,【,3,5,6,9,13,，,27,31,】,11,【,3,5,6,9,11,，,13,，,27,31,】,例,（,13,，,6,，,3,，,31,，,9,，,27,，,5,，,11,）,21,21,25,49,25*,16,08,0 1 2 3 4 5 6,暂,存,21,i,=2,i,=3,i,=5,i,=4,i,=6,25,25,49,49,25*,25*,49,16,16,25*,08,08,49,21,25,49,25*,21,初态：,16,49,25*,25,21,16,08,完成,!,将序列存入顺序表,L,中，将,L.r0,作为哨兵,（,21,，,25,，,49,，,25,*,，,16,，,08,）,*,表示后一个,25,22,例 设数据序列（一组关键字）为：,31,，,43,，,9,，,54,，,16,，,27,，,5,，,43,，对其进行直接插入排序，请写出每一趟的排序结果。

分析：该记录序列的直接插入排序的过程和每一趟的排序结果如下图所示23,24,25,26,利用,“,顺序查找,”,实现,“,在,R1.i-1,中,查找,Ri,的插入位置,”,27,从,Ri-1,起向前进行顺序查找，,监视哨设置在,R0,；,R0=Ri;/,设置“哨兵”,循环结束表明,Ri,的插入位置为,j+1,R0,j,Ri,for,(j=i-1;R0.keyRj.key;,-,j);,/,从后往前找,j=i-1,插入位置,28,对于在查找过程中找到的那些关键字不小于,Ri.key,的记录，并在查找的同时实现记录向后移动；,for,(j=i-1;R0.keyRj.key;,-,j);,Rj+1=Rj,R0,j,Ri,j=i-1,上述循环结束后可以直接进行“插入”,插入位置,29,令,i=2,，,3,，,n,实现整个序列的排序for,(i=2;i=n;+i),if,(Ri.keyRi-1.key),在,R1.i-1,中查找,Ri,的插入位置,;,插入,Ri;,30,void,InsertionSort(SqList&L),/,对顺序表,L,作直接插入排序for,(i=2;i=L.length;+i),if,(L.ri.key L.ri-1.key),/InsertSort,L.r0=L.ri;/,复制为监视哨,for,(j=i-1;L.r0.key L.rj.key;-j),L.rj+1=L.rj;,/,记录后移,L.rj+1=L.r0;/,插入到正确位置,例如，,n=6,，数组,R,的六个排序码分别为：,17,，,3,，,25,，,14,，,20,，,9,。

它的直接插入排序的执行过程如图,9-1,所示32,内部排序的,时间分析,：,实现内部排序的,基本操作,有两个：,（,2,）,“移动”,记录1,）,“比较”,序列中两个关键字的大小；,33,对于直接插入排序：,最好的情况（关键字在记录序列中顺序有序）：,“,比较”,的次数：,最坏的情况（关键字在记录序列中逆序有序）：,“,比较”,的次数：,0,“,移动”,的次数：,“,移动”,的次数：,34,因为,R1.i-1,是一个按关键字有序的有序序列，则可以,利用,折半查找,实现“在,R1.i-1,中,查找,Ri,的,插入位置,”,，如此实现的插入排序为,折半插入,排序二、折半插入排序,【,效果,】,减少关键字间的比较次数35,i,low,high,m,m,low,low,m,high,i,low,high,m,high,m,high,m,low,例如,:,再如,:,插入,位置,插入,位置,14 36 49 52 80,58,61 23 97 75,L.r,14 36 49 52 58 61 80,23 97 75,L.r,36,void,BiInsertionSort(SqList&L),/BInsertSort,在,L.r1.i-1,中折半查找插入位置；,for,(i=2;i=high+1;-j),L.rj+1=L.rj;/,记录后移,L.rhigh+1=L.r0;/,插入,37,low=1;high=i-1;,while,(low,=,high),m=(low+high)/2;/,折半,if,(L.r0.key L.rm.key),high=m-1;,/,插入点在低半区,else,low=m+1;,/,插入点在高半区,38,三、希尔排序（又称缩小增量排序）,希尔排序,又称为“缩小增量排序”。

是,1959,年由,D.L.Shell,提出来的基本思想是：,1,、选定一个记录下标的增量,d,，将整个记录序列按增量,d,从第一个记录开始划分为若干组，对每组使用直接插入排序的方法；,2,、减小增量,d,，不断重复上述过程，如此下去，直到,d,=1(,此时整个序列是一组,),39,先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的因此希尔排序在时间效率上比前两种方法有较大提高具体做法为：,40,将记录序列分成若干子序列，分别对每个子序列进行插入排序其中，,d,称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序,减为,1,例如：将,n,个记录分成,d,个子序列：,R1,，,R1+d,，,R1+2d,，,，,R1+kd,R2,，,R2+d,，,R2+2d,，,，,R2+kd,Rd,，,R2d,，,R3d,，,，,Rkd,，,R(k+1)d,41,例如：,16 25 12 30 47 11 23 36 9 18 31,第一趟希尔排序，设增量,d=5,11,23,12,9,18,16,25,36,30,47,31,第二趟希尔排序，设增量,d=3,9,18,12,11,23,16,25,31,30,47,36,第三趟希尔排序，设增量,d=1,9 11 12 16 18 23 25 30 31 36 47,例如，,n=8,，数组,array,的八个元素分别为：,91,，,67,，,35,，,62,，,29,，,72,，,46,，,57,。

给出希尔排序算法的执行过程43,希尔排序,子序列的构成,不是,简单地“,逐段分割,”,将相隔,某个增量,dk,的记录组成一个子序列,让,增量,dk,逐趟缩短,（例如依次取,5,3,1,）,直到,dk,1,为止技巧：,小元素,跳跃式,前移,最后一趟增量为1时，序列已基本有序,平均性能优于,直接插入排序,优点：,44,。