chapter10-Sort.ppt

单击此处编辑母版标题样式,*,*,第,10,章 内部排序,授课教师：胡平,计算机科学与工程系，,2009,2026/3/5 周四,1,条件,1,：,记录必须以,顺序结构,存储,条件,2,：,记录必须,有序,折半查找的条件,high=9,low=1,mid=5,查找“,4”,2026/3/5 周四,2,【,目的,】,：,理解各种,排序算法,的算法思想，能,用它们求解现实生活中与排序有关的问题。,【,内容,】,：,排序的有关,概念,、,分类,、,直接插入排序,、,希尔,排序、快速排序、归并排序,的,算法思想,、,描,述,，以及,效率,和,稳定性,。,【,重点,】,：,上述,4,种排序方法的,算法思想,。,【,难点,】,：,希尔排序、归并排序的,算法思想,。,关于本讲,2026/3/5 周四,3,排序,：将若干记录,按关键字,以非递减（或非递增）的顺序进行排列的操作。,正序,：记录按关键字以,非递减,顺序排列。,逆序,：记录按关键字以,非递增,顺序排列。,稳定性,：对任一序列，若序列中,关键字相同,的记录的,先后关系,在排序前后,总,一致，则该排序算法是,稳定,的。,反之，则为不稳定的。,有关的概念,2,，,3,，,2,，,1,排序算法,A,1,，,2,，,2,，,3,2,，,3,，,2,，,1,排序算法,B,1,，,2,，,2,，,3,(A,不稳定,),(,尚不能判断,B,是否稳定,),1,，,2,，,2,，,3,3,，,2,，,2,，,1,2026/3/5 周四,4,排序方法的分类,内部排序,：,排序方法,待排序的记录,全部存,放在内存,中。,外部排序,：,待排序的记录,部分存,放在外存,中。,插入排序,快速排序,选择排序,归并排序,基数排序,2026/3/5 周四,5,直接插入排序的算法思想,打扑克,(,不计花色,),：右手每起一张牌，按牌面大小插入到左手已有序的若干张牌中的合适位置，直至所有的牌起完。,对,R,1,R,2,R,i,R,n,进行直接插入排序,：,每次将一个记录插入到,当前已有序,的子序列,(,即,有序区,),，直至所有记录插入完毕。,将,R,i,插入到有序区的操作称为,第,i,趟,直接插入。,抽象,2026/3/5 周四,6,直接插入排序的算法思想,开始,结束,将,R,i,插入到,R,1,R,i-1,i,2,i,i+1,否,是,i,n?,待排序列,i=2,i=3,i=4,有序区,无序区,第,i,趟直接插入的关键是：,在有序区,R,1,R,i-1,中，找到,R,i,的插入位置。,1 2 3 4,2026/3/5 周四,7,第,i,趟直接插入,开始,结束,R,i,R,j,?,j,i-1,R,j,后移,否,是,R,i,放在,j+1,位置,j,j-1,开始,结束,将,R,i,插入到,R,1,R,i-1,i,2,i,i+1,否,是,i,n?,第,i,趟直接插入的算法思想,2026/3/5 周四,8,直接插入排序算法演示,【,观看演示,】,2026/3/5 周四,9,待排序记录的存储结构,0,分量不存放记录,typedef,struct,int,key;,.;,RecorderType,;,/,记录的关键字,/,其他信息,/,自定义的记录类型,typedef,struct,RecorderType,r100;,int,length;,SqList,;,/100,为最大容量,/,记录实际个数,/,多个记录构成的顺序表,2026/3/5 周四,10,直接插入排序算法的类,C,描述,j,i-1,否,R,i,放在,j+1,位置,开始,是,i,n?,i,2,R,i,R,j,?,R,j,后移,是,j,j-1,否,结束,i,i+1,【,观看演示,】,void,InsertSort,(),SqList,L,for,(),i=2;,i=,L.length,;,i+,if(L.ri.key,L.ri-1.key),L.r,0,=,L.ri,;,for,(),j=i-1;,L.ri.key,L.rj.key,;,j-,L.rj+1=,L.rj,;,L.rj+1=L.r,0,；,L.r,0,.keyj,时，,d,i,0,且,R,i,0,且,R,i,R,j,?,R,j,后移,是,j,j-d,否,结束,i,i+1,void,ShellInsert,(),SqList,L,for,(),i=d+1;,i=,L.length,;,i+,if(L.ri.key,L.ri-d.key,),L.r,0,=,L.ri,;,for,(,),j=,i-d,;,L.ri.key,L.rj.key,;,j-=d,L.rj+d,=,L.rj,;,L.rj+d,=L.r,0,；,L.r,0,.key0&,2026/3/5 周四,19,for(),希尔排序的类,C,描述,void,ShellInsert,(SqList,L,int,d),.,ShellSort,(SqList,L,int,D,int,k),ik;,i+,ShellInsert,(L,Di,);,i=0;,void,2026/3/5 周四,20,增量序列的选取,最优的,增量序列选取方法很复杂，涉及到数学上,至今尚未解决,的难题。,增量序列一般要满足：,各增量间,没有,除,1,之外的,公因子,。,最后,一个增量一定是,1,.,2026/3/5 周四,21,希尔排序的时间复杂度,依赖于所选取的增量序列。,当,n,较大时，关键字比较和移动的次数约在,n,l.25,到,1.6*n,1.25,之间。,一般情况下，认为希尔排序的时间复杂度近似为,O(n,1.3,),。,2026/3/5 周四,22,算法小结,希尔插入排序同样由,若干趟,组成。,一趟,增量为,d,的希尔排序中，同一组,相邻记录,的下标之差为,d,。,注意,内层,for,循环的,第二个表达式,。,r0,的作用：,仅暂存,ri,。,算法的时空复杂度及稳定性。,2026/3/5 周四,23,学习回顾（插入排序）,每趟的关键是找到,待插入记录,在当前已有序的记录中的,合适位置,。,在排序过程中，直接插入排序是“,一步步,”地移动记录；希尔排序则是呈“,跳跃式,”的。,2026/3/5 周四,24,冒泡排序,算法思想,：排序分为若干趟，每趟,找到,若干记录中关键字,最大,(,或,最小,),的记录，并将其放在,合适位置,。,相邻,两记录比较时，可能发生“,交换,”。,对,n,个记录进行“冒泡排序”，,最坏情况,下要执行,n-1,趟，时间复杂度为,O(n,2,),。,“冒泡排序”,结束条件,是：某一趟排序中，,没有,任何记录发生“,交换,”。,不足,：关键字较小的记录是“,一步步,”向前“挪动”。,第一趟,第二趟,第三趟,第四趟,2026/3/5 周四,25,快速排序的算法思想,排序分为若干趟，每一趟选一个记录,(,基准,/,枢轴，,pivot,),，将所有记录分为,两块,，使,第一块,中所有记录的关键字,均不大于,基准,，,第二块,中所有记录的关键字,均不小于,基准,；,然后分别对,两块,继续,下一趟,排序。,基准：,4,基准：,2,和,6,基准：,4,2026/3/5 周四,26,一趟快速排序,/,划分,i,j,p,=4,i,j,i,j,p,=2,p,=6,i,j,p,=4,开始,否,是,i,j?,自,j,向左,找,小于,p,的记录,R,j,放在,i,位置,i,i+1,i,j?,自,i,向右,找,大于,p,的记录,R,i,放在,j,位置,j,j-1,是,p,放在,i,位置,否,结束,2026/3/5 周四,27,快速排序算法演示,【,观看演示,】,2026/3/5 周四,28,一趟划分的类,C,描述,【,观看演示,】,int,Partition,(),SqList,L,while,(),i=L.r,0,.key,while,(),i+;,L.rj,-=,L.ri,;,L.ri.key=L.r0.key,L.ri,=L.r,0,；,return,i;,&ij,&i=L.ri.key,2026/3/5 周四,29,QuickSort,();,快速排序的类,C,描述,void,QuickSort,(),给定若干记录，,难以确定,要执行,多少趟,划分。,一趟划分,和对其划分出来的,两个块继续划分,，这两个过程具有,相同的性质,，只是记录个数（即,问题规模,）不同，故可采用,递归,来描述快速排序。,若某个块只包含,一个记录,，则该块,不需要继续划分,。,SqList,L,Partition,();,L,i,j,int,i,int,j,L,i,p-1,QuickSort,();,L,p+1,j,if,(i,j),p=,2026/3/5 周四,30,快速排序的复杂度,空间复杂度,：,O(1),。,除,r0,，还会用到一个,递归工作栈,。,时间复杂度,：,一般情况,下，快速排序的时间复杂度为,O(n,*,ln,n,),（,P,276-277,），是所有内部排序算法中时间效率,最高,的，快速排序也因此而得名。,最坏情况,下，每趟划分所选取的,基准,都是当前块中关键字,最小,的记录，此时快速排序,退化,成,冒泡排序,，时间复杂度为：,O(n,2,),。,2026/3/5 周四,31,基准的选取,前述的划分算法均将,块首,记录作为,基准,。,通过选取当前块的,首,、,尾,、,中间,位置记录三者关键字,居中,的记录作为,基准,，然后,交换,基准,和,块首,记录，可以进一步提高效率。,2026/3/5 周四,32,算法小结,快速排序基于,交换,的策略，由若干趟,划分,组成。,相比较于冒泡排序，快速排序在交换时，记录呈“,跳跃式,”挪动。,算法采用了,递归,，当块仅包含,一个记录,时，递归返回。,算法的时空复杂度及稳定性。,2026/3/5 周四,33,学习回顾（快速排序）,排序可分为,若干趟划分,，每趟划分将记录分为,两块,，,块间,是,有序,的。,算法采用了,递归,，当,块仅包含一个记录,时，,递归结束,。,2026/3/5 周四,34,归并排序,算法思想,：基于“,合并,”的策略，将若干个,有序,的子序列经过若干趟合并，最终,合并,成,一个,有序序列。,最常见的归并排序是,2-,路归并排序,。,2026/3/5 周四,35,2-,路归并排序的算法思想,算法分为若干趟，,每一趟,将若干,位置相邻,的,两个有序的,子序列,合并,成,一个有序的,子序列，再进行,下一趟,归并，直至得到,一个有序的序列,。,2026/3/5 周四,36,合并的思想,还记得第,2,章中,合并,两个,有序的顺序表,吗？,开始,将,S,i,存放到,T,中,p,位置,i,p,low,j,m+1,i,i+1,是,i,m,且,j,high,?,结束,S,i,S,j,?,将,S,j,存放到,T,中,p,位置,j,j+1,p,p+1,是,否,否,将,S1,或,S2,中剩余记录放到,T,中,m,m+1,high,low,low,high,i,j,p,S1,S2,S,T,2026/3/5 周四,37,合并算法演示,【,观看演示,】,2026/3/5 周四,38,2-,路归并排序的递归形式,一趟归并,和对其划分出来的,两个子序列继续归并,，这两个过程具有,相同的性质,，只是记录个数（即,问题规模,）不同，故采用,递归,形式来描述归并排序较容易理解。,若某个子序列只包含,一个记录,，则,不需要,继续归并。,2026/3/5 周四,39,合并算法的类,C,描述,【,观看演示,】,void,Merge,(),SqList,S,while,(),int,low,int,high,i,=m,&,j,=high,T.rp,+=,S.r,i,+,;,S.ri,=,T.r,p,；,开始,i,p,low,j,m+1,i,m,且,j,high,?,将,S,i,存放到,p,位置,是,i,i+1,j,j+1,p,p+1,S,i,S,j,?,是,将,S,j,存放到,p,位置,否,结束,否,将,S1,或,S2,中剩余记录放到,T,中,SqList,T,int,m,i,=low;,j,=m+1;,p=low;,if,(),S.r,i,.key,=,S.r,j,.key,T.rp,+=,S.r,j,+,;,else,while,(),i,=m,T.rp,+=,S.r,i,+,;,while,(),j,=high,T.rp,+=,S.r,j,+,;,for,(),p=low,i=low;,i=high;,p+,i+,2026/3/5 周四,40,归并排序的类,C,描述,(,递归形式,),void,MergeSort,(),SqList,L,int,low,int,high,Merge,();,L,T,low,if,(low,high),设当前子序列是,Rlow,.high,。,将当前子序列一分为二：,Rlow,.m,和,Rm+1.high,；,递归,地两个子序列进行归并排序；,合并,上述两个子序列。,SqList,T,m,=(low+high)/2;,MergeSort,();,L,T,low,m,MergeSort,();,L,T,m+1,high,m,high,2026/3/5 周四,41,归并排序的复杂度,空间复杂度,：,引入了辅助空间,T,，大小和,S,相同,。故空间复杂度为,O(n,),。,时间复杂度,：,共需,log,2,n,趟归并。,每趟,归并过程中，都要将,所有,记录存放在辅助空间,T1.n,中。,O(nlog,2,n,),2026/3/5 周四,42,各排序方法的比较,2026/3/5 周四,43,