第八章-排序A.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章,排序,(之一),数据结构课程的内容,8.1,基本概念,8.2,插入排序,8.3,交换排序,8.4,选择排序,8.5,归并排序,8.6,基数排序,内部排序内容简介,:,排序基本概念,:,排序：,给定一组,记录,的集合,r,1,r,2,r,n,，,其相应的关键码分别为,k,1,k,2,k,n,，,排序是将这些记录排列成顺序为,r,s,1,r,s,2,r,sn,的一个序列，使得相应的关键码满足,k,s,1,k,s,2,k,sn,（,称为升序）或,k,s,1,k,s,2,k,sn,（,称为降序）。,正序：,待排序序列中的记录已按关键码排好序。,逆序（反序）：,待排序序列中记录的排列顺序与排好序的顺序正好相反。,排序算法的,稳定性：,假定在待排序的记录集中，存在,多个,具有,相同键值,的记录，若,经过排序,，这些记录的,相对次序,仍然,保持不变,，即在原序列中，,k,i,=,k,j,且,k,i,在,k,j,之前，而在排序后的序列中，,k,i,仍在,k,j,之前，则称这种排序算法是,稳定的,；,否则,称为,不稳定,的。,排序基本概念,:,单键排序：,根据一个关键码进行的排序；,多键排序：,根据多个关键码进行的排序。,学号,姓名,高数,英语,思想品德,0001,王 军,85,88,0002,李 明,64,92,0003,汤晓影,85,86,68,72,78,按学号排序,单键排序,按成绩（高数英语思想品德）排序,多键排序,排序的分类,1.,内部排序：,在排序的整个过程中，待,排序的所有记录,全部,被放置在,内存,中。,2.,外部排序,：,由于待排序的记录个数太多，不能同时放置在内存，而需要将,一部分记录,放置,在内存,，,另一部分记录,放置,在外存上,，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。,d,关键字的位数,(,长度,),按排序算法的时间复杂度不同，可分为,3,类：,简单的排序算法：时间效率低，,O(n,2,),先进的排序算法,:,时间效率高，,O(nlog,2,n)基数排序算算法：时间效率高，,O(dn),待排序记录在内存中怎样存储和处理？,顺序,排序,排序时直接移动记录；,链表,排序,排序时只移动指针；,地址,排序,排序时先移动地址，最后再移动记录。,1,.,内排序在排序过程中的,基本操作,：,比较,：关键码之间的比较；,移动,：记录从一个位置移动到另一个位置。,2.,辅助存储空间,。,3.,算法本身的复杂程度,。,排序算法的,性能,顺序存储结构类,定义如下：,class,elem,friend class,seqlist,;,T1 key;,T2 other;,;,template,class,seqlist,elem,*,data,;,int,n/,长度,public:,seqlist(int,n1);,insertsort,();,;,8.2,插入排序,插入排序的,基本思想,是：,插入排序有多种具体实现算法：,1),直接插入排序,2),二分,插入排序,3),表插入排序,4),希尔排序,每步将一个待排序的对象，按其关键码大小，,插入,到前面,已经排好序的一组对象,的,适当位置,上，直到对象全部插入为止。,简言之，边插入边排序，保证子序列中随时都是排好序的。,1),直接插入排序,新元素插入到哪里？,例,1,：,关键字序列,T=,（,13,，,6,，,3,，,31,，,9,，,27,，,5,，,11,），,请写出直接插入排序的中间过程序列。,【,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,】,在已形成的,有序表中线性查找,，并在适当位置插入，把原来位置上的元素向后,顺移,。,最简单的排序法！,直接插入排序算法：,template,void,seqlist,:,insertsort,(),/,顺序存储表示的直接插入排序算法,int,i,j,;,for(i,=2;i=,n;i,+)/,设,i=1,已排序,data0=,datai,;/,哨兵,j=,i-1,;,/,从已排序的序列最后一位开始向前比较,while(data0.key,dataj.key,),dataj+1=,dataj,-,;,/,顺序查找插入点，移动腾出位置,dataj+1,=data0;/,插入插入点,直接插入排序,算法性能分析,最好情况下（,正序,）：,1,2,3,4,5,时间复杂度为,O,(,n,),。,比较次数：,n,-1,移动次数：,2(,n,-1),1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,3,4,5,最坏,情况下（逆序或反序）：,时间复杂度为,O,(,n,2,),。,5,4,3,2,1,4,5,3,2,1,3,4,5,2,1,2,3,4,5,1,1,2,3,4,5,4,3,2,1,比较次数：,移动次数：,2,),1,)(,2,(,2,-,+,=,=,n,n,i,n,i,2,),1,)(,4,(,2,-,+,=,+,n,n,i,n,2,=,i,）,（,平均,情况下（随机排列）：,平均时间复杂度为,O,(,n,2,),。,比较次数：,移动次数：,4,),1,)(,4,(,-,+,=,n,n,n,2,=,i,4,),1,)(,2,(,2,-n,n,n,i,i,2,（,2,2,+,i,）,若待排序对象序列中出现各种可能排列的,概率相同,，则可取上述,最好情况,和,最坏情况,的,平均,情况。,小结：直接插入排序是一种,稳定,的排序算法。,),二分插入排序,在已形成的,有序表中,二分查找,，并在,适当位置插入,，把原来位置上的元素,向后顺移,。,新元素插入到哪里？,例：设待排序的记录共,8,个,键值分别为,30,13,70,85,39,42,6,20,优点：,比较的次数大大减少，全部元素比较次数仅为,O(nlog,2,n),。平均为（,log,2,n),时间效率：,虽然比较次数大大减少，可惜,移动次数,并,未减少,，所以排序效率仍为,O(n,2,),。,空间效率：,O,（,1,）,稳定性：稳定,二分法插入第,8,个记录,20,的比较和插入过程排序示例,:,序号,:1 2 3 4 5 6 7 8,键值,:6 13 30 39 42 70 85 20,t=1 m=4 w=7,用二分法,2013,t=w=m=3,20w,查找结束,t=3,为插入位置,插入,20,6 13 20 30 39 42 70 85,二分插入排序算法：,template,void,seqlist,:,ef_sort,(),/,二分法插入排序,int,i,j,m,l,h,;,for(,i,=2;i=,n,;i,+),data0.key=,datai.key,;/,哨兵,l=1;h=i-1;,while(,l,=h,)/,利用二分查找方法找到插入点,m=(l+h)/2;,if(,data0.key=,l;j,-,)/,找到插入后，移动数据,dataj+1=,dataj,;,datal,=data0;,）,希尔（,shell,）排序,（又称缩小增量排序）,基本思想,：先,取定,一个,正整数,d,1,n,把,全部记录分成,d,1,个组,，所有,距离为,d,1,倍数的记录,放,在一组,中，,在各组内,进行,插入排序,；然后,取,d,2,=1,;d=,d/2,),以,d,为增量，进行组内直接插入排序；,解决方法：,在插入记录,ri,时，自,ri-d,起往前跳跃式（跳跃幅度为,d,）,搜索待插入位置，并且,r0,只是暂存单元，不是哨兵。当搜索位置,0,，表示插入位置已找到。,在搜索过程中，记录后移也是跳跃,d,个位置。,在整个序列中，前,d,个记录分别是,d,个子序列中的第一个记录，所以从第,d+1,个记录开始进行插入。,关键问题,(2),：子序列内如何进行直接插入排序？,关键算法描述：,for(i=,d+1,;i0&data0.key,dataj.key,),data,j+d,=,dataj,;/,记录后移,d,个位置,j=,j-d,;/,比较同一子序列的前一个记录,data,j+d,=data0;,希尔排序算法的,时间性能：,希尔排序,算法的时间性能是所取,增量,的函数，而到目前为止尚未有人求得一种最好的增量序列。,研究表明，希尔排序的时间性能,在,O,(,n,2,),和,O,(,nlog,2,n,),之间,。当,n,在某个特定范围内，希尔排序所需的比较次数和记录的移动次数,约为,O,(,n,1,.,3,),。,课堂练习：,1,、,欲将序列（,Q,H,C,Y,P,A,M,S,R,D,F,X,）,中的关键码按字母升序重排，则初始步长为,4,的希尔排序一趟的结果是？,答：,原始序列：,Q,H,C,Y,P,A,M,S,R,D,F,X,shell,一趟后：,2,、,以关键字序列（,256,，,301,，,751,，,129,937,，,863,，,742,，,694,，,076,，,438,）为例，分别写出执行以下算法的,各趟,排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？,直接插入排序,希尔排序（取,d,k,=5,3,1,）,P,Q,R,A,D,H,C,F,M,S,X,Y,答：,显然，直接插入排序方法易于在链表上实现；但希尔排序方法因为是按增量选择记录，不易于在链表上实现。,两种排序方法的中间状态分别描述如后：,原始序列,：,256,，,301,，,751,，,129,，,937,，,863,，,742,，,694,，,076,，,438,256,301,，,751,，,129,，,937,，,863,，,742,，,694,，,076,，,438,256,，,301,751,129,，,937,，,863,，,742,，,694,，,076,，,438,129,，,256,，,301,，,751,，,937,，,863,，,742,，,694,，,076,，,438,129,，,256,，,301,，,751,，,937,，,863,，,742,，,694,，,076,，,438,129,，,256,，,301,，,751,，,863,，,937,，,742,，,694,，,076,，,438,129,，,256,，,301,，,742,751,，,863,，,937,，,694,，,076,，,438,129,，,256,，,301,，,694,，,742,，,751,，,863,，,937,，,076,，,438,076,，,129,，,256,，,301,，,694,，,742,，,751,，,863,，,937,，,438,076,，,129,，,256,，,301,，,438,，,694,，,742,，,751,，,863,，,937,直接插入排序,第,1,趟,第,2,趟,第,3,趟,第,4,趟,第,5,趟,第,6,趟,第,7,趟,第,8,趟,第,9,趟,原始序列：,256,，,301,，,751,，,129,，937,，,863,，,742,，,694,，,076,，,438,希尔排序,(,取,dk,=5,3,1),256,，,301,，,751,，,129,，,937,，,863,，,742,，,694,，,076,，,438,256,，,301,，,751,，,129,，,937,，,863,，,742,，,694,，,076,，,438,256,，,301,，,694,，,129,，,937,，,863,，,742,，,751,，,076,，,438,256,，,301,，,694,，,076,，,937,，,863,，,742,，,751,，,129,，,438,256,，,301,，,694,，,076,，,438,，,863,，,742,，,751,，,129,，,937,第,1,趟,d,k,=5,第,2,趟,d,k,=3,第,3,趟,d,k,=1,256,，,301,，,694,，,076,，,438,，,863,，,742,，,751,，,129,，,937,256,，,301,，,694,，,076,，,438,，,863,，,742,，,751,，,129,，,937,076,，,301,，,694,，,256,，,438,，,863,，,742,，,751,，,129,，,937,076,，,301,，,694,，,256,，,438,，,863,，,742,，,751,，,129,，,937,076,，,301,，,694,，,256,，,438,，,863,，,742,，,751,，,129,，,937,076,，,301,，,129,，,256,，,438,，,694,，,742,，,751,，,863,，,937,076,，,301,，,129,，,256,，,438,，,694,，,742,，,751,，,863,，,937,076,，,301,，,129,，,256,，,438,，,694,，,742,，,751,，,863,，,937,076,，,129,，,256,，,301,，,438,，,694,，,742,，,751,，,863,937,8.3,交换排序,插入排序的,基本思想,是：,两两比较,待排序记录的关键码，如果,发生逆序,（即排列顺序与排序后的次序正好相反），则,交换之,，直到所有记录都排好序为止。,交换排序的主要算法有：,1),冒泡排序,2),快速排序,1),冒泡排序,基本思路：,每趟不断将记录,两两比较,，并按,“,前小后大,”,（或,“,前大后小,”,）规则交换。（两两比较待排序记录的键值，并交换不满足顺序要求的那些偶对，直到全部满足顺序要求为止。）,优点：,每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；,一旦下趟没有交换发生，还可以提前结束排序,。,前提：顺序,存储结构,0598,12,69,38,53,81,起泡排序过程示例,:,05,98,12,69,38,53,81,05,98,12,69,38,53,81,05,98,12,69,38,53,81,注：下趟没有交换发生，还可以提前结束排序,。,课堂练习：,关键字序列,T=(21,，,25,，,49,，,25,*,，,16,，,08,），,请写出冒泡排序的具体实现过程。,21,，,25,，,49,，,25,*,，,16,，,08,21,，,25,，,25*,，,16,，,08,，,49,21,，,25,，,16,，,08,，,25*,，,49,21,，,16,，,08,，,25,，,25*,，,49,16,08,，,21,，,25,，,25*,，,49,08,，,16,，,21,，,25,，,25*,，,49,初态：,第,1,趟,第,2,趟,第,3,趟,第,4,趟,第,5,趟,如何起泡排序需多少趟,每趟需循环次数,?,第,1,趟,:n-1,次,第,2,趟,:n-2,次,(,至多,),第,n-1,趟,:1,次,template,void,seqlist,:,mp_sort,(),/,冒泡排序，从小到大,int,i,j,k,;,elem,x;,j=1;k=1;,while(,j,0,),k=0;/,计数每趟交换次数，若为,0,，则可以停止,for(i,=1;i=,n-j;i,+),if(datai+1.keydataj+1.key,）,datajdataj+1,；,exchange=,j,；,解决方法：,设,bound,位置的记录是无序区的最后一个记录，则每趟起泡排序的范围是,data1,databound,。,在一趟排序后，从,exchange,位置之后的记录一定是有序的，所以,bound=exchange,。,关键问题,：,如何确定起泡,排序的范围,？,05,98,12,69,38,53,81,05,98,69,81,12,交换,38,交换,53,交换,关键算法描述：,bound=,exchange,;,for(j=1;jdataj+1.key,）,dataj,dataj+1,；exchange=,j,；,05,98,12,69,38,53,81,解决方法：,在每一趟起泡排序之前，令,exchange,的初值为,0,，在以后的排序过程中，只要有记录交换，,exchange,的值就会大于,0,。这样，在一趟比较完毕，就可以通过,exchange,的值是否为,0,来判别是否有记录交换，从而判别整个起泡排序的结束。,关键问题,：,如何判别,起泡排序的结束,？,关键算法描述：,while(,exchange,),bound=exchange;,for(j=1;jdataj+1.key,）,dataj,dataj+1,；,exchange=j,；,void,BubbleSort,(,int,r,int,n,),exchange=n;,while,(,exchange,),bound=exchange;,exchange=0,；,for,(,j=1;jrj+1,),rjrj+1,；,exchange=j,；,起泡排序算法,2,）快速排序,从待,排序列中任取一个元素,(,例如取,第一个,),作为,中心,，所有,比它小,的元素,一律前放,，所有,比它大,的元素,一律后放,，,形成,左右两个子表,；然后,再对各子表重新选择中心元素,并依此规则调整，直到,每个子表的元素只剩一个,。此时便为,有序序列,了。,基本思想：,优点：,因为,每趟可以确定不止一个元素,的位置，而且呈,指数增加,，所以,特别快,！,前提：,顺序存储结构,例,1,：快速排序,第一趟,排序,示例,15 20 11 10 23 13,20 11 10 23 13,i j,1513,交换，,i=i+1,13 20 11 10 23 15,i j,2015,交换，,j=j-1,15 11 10 23 20,i j j,1510,交换，,i=i+1,13 10 11 15 23 20,i i j,11,15,i=i+1;i=j,第一趟结果：,13 10 11 15 23 20,第二趟结果：,11 10 13 15 23 20,第三趟结果：,10 11 13 15 23 20,第四趟结果：,10 11 13 15 20 23,第一趟结果：,13 10 11 15 23 20,(),，,设以首元素为枢轴中心,例,1,：,关键字序列,T=(21,，,25,，,49,，,25,*,，,16,，,08,），,请写出快速排序的算法步骤。,21,，25，49，25,*,，16，08,初态：,第,1,趟：,第,2,趟：,第,3,趟：,08,，,16,，,21,，,25,，,25*,，,(,49,),21,16,，,08,，,(),25,，,25*,，,49,(,08,),，,16,，,21,，,25,，,(,25*,，,49,),Low=high=,3,，,本趟停止，将支点定位并返回位置信息,例,2,：,关键字序列,T=(21,，,25,，,49,，,25,*,，,16,，,08,），,请写出快速排序算法的一趟实现过程。,ri,0,1,2,3,4,5,6,初态,21,25,49,25,*,16,08,第,1,趟,high,low,21,21,21,21,21,25,*,3,21,pivotkey,=,21,08,25,16,49,(08,，16）,21,（25,*,，49，25 ）,25,*,跑到了前面，不稳定！,low,high,low,high,high,解决方法：,设待划分的序列是,datas,-,datat,，,设参数,i,，,j,分别指向子序列左、右两端的下标,s,和,t,，,令,datas,为轴值，,（,1,）,j,从后,向前,扫描，直到,dataj,datai,，,将,dataj,移动到,datai,的位置，使,关键码小,（同轴值相比）的记录,移动到前面去,；,（,2,）,i,从前,向后,扫描，直到,datai,dataj,，,将,datai,移动到,dataj,的位置，使,关键码大,（同轴值比较）的记录,移动到后面,去；,（,3,）重复上述过程，直到,i=j,。,关键问题,(1),：如何实现一次划分？,快速排序算法分析,(,了解,),算法描述如下：,int,Partition(,int,first,int,end),i=first;j=end;/,初始化,while(ij),while(ij&,datai,=,dataj,)j-,；,/,右侧扫描,if(ij),dataidataj,;i+;/,将较小记录交换到前面,while(ij&,datai,=,dataj,)i+,；,/,左侧扫描,if(ij),datajdatai,;j-;/,将较大记录交换到后面,retutn,i;/i,为轴值记录的最终位置,解决方法：,对分割得到的两个子序列递归地执行快速排序。,关键问题,：如何处理分割得到的两个待排序子序列？,13,27,38,65,50,49,55,13,27,50,38,49,55,65,i,j,i,j,void,QuickSort,(,int,firstint,end),/,在序列,firstend,中递归地进行快速排序,if(first end),pivotpos,=Partition(first,end);,QuickSort,(first,pivotpos-1);,QuickSort,(pivotpos+1,end);,算法描述：,例：,38,27,55,50,13,49,65,的快速排序递归树如下：,38,13,50,55,49,65,27,快速排序的,递归执行过程,可以用递归树描述。,快速排序的时间性能分析,快速排序算法,效率分析,：,快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数,（新的,low,和,high,）,可以证明，函数,quicksort,的,平均时间复杂度是,O(,n,log,2,n,),。,实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有,内排序方法中最好的一,个,。,若待排序序列建值已排序，会出现,最坏情况,，时间复杂度为,O(n,2,),。（改进方法，不选第一个元素作为基准记录）,最大递归调用层次数,与,递归树的深度一致,，理想情况为,log,2,(,n,+1),。,因此，要求,存储开销为,o(log,2,n,),。最坏是,O(n,).,如果每次划分对一个对象定位后，该对象的,左侧子序列,与,右侧子序列的长度相同,，则下一步将是对两个长度减半的子序列进行排序，这是,最理想的情况,。此时，快速排序的,趟数最少,。,在,最坏的情况,，即待,排序对象序列已经按其关键码从小到大排好序的情况,下，,其,递归树成为单支树,，每次划分只得到一个比上一次少一个对象的子序列。这样，必须经过,n,-1,趟才能把所有对象定位，而且第,i,趟需要经过,n,-,i,次关键码比较才能找到第,i,个对象的安放位置，,总的关键码比较次数将达到,n,2,/2,快速排序,是一个,不稳定的排序方法,讨论,.“,快速排序”是否真的比任何排序算法都快？,设每个子表的支点都在中间（比较均衡），则：,第,1,趟比较，可以确定,1,个元素的位置；,第,2,趟比较（,2,个子表），可以再确定,2,个元素的位置；,第,3,趟比较（,4,个子表），可以再确定,4,个元素的位置；,第,4,趟比较（,8,个子表），可以再确定,8,个元素的位置；,只需,log,2,n,1,趟便可排好序。,基本上是！因为每趟可以确定的数据元素是呈指数增加的！,而且，每趟需要比较和移动的元素也呈指数下降，加上编程时使用了交替逼近技巧，更进一步减少了移动次数，所以速度特别快。,待续！,