数据结构ppt7

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 排序,7.1,概述,7.2,插入排序,7.3,交换排序,7.4,选择排序,7.5,归并排序,7.1,概述,7.1.1,排序及其分类,排序：,将数据表调整为按,关键字,从小到大,(,或从大到小,),的次序排列的过程。,排序的分类：,（,1,）按大小方向的不同，可分为增排序和减排序。,（,2,）按排序过程中所有数据是否完全在内存中，可分为内部排序和外部排序。,（,3,）按排序过程中相同数据的相对次序是否改变，可分为稳定排序和不稳定排序。,（,4,）对内部排序，按排序策略不同，可分为插入排序、交换排序、选择排序、归并排序等。,7.1,概述,7.1.2,排序算法的分析指标,侧重于其时间性能和空间性能方面。,（,1,）时间性能：主要以算法中用得最多的基本操作,(,主要是比较、移动或交换元素,),的执行次数,(,或其数量级,),来衡量。,（,2,）空间性能：主要是排序过程中所占用的辅助空间的情况，即是用来临时存储数据的内存情况。,7.2,插入排序,基本思想,将待排序表分成左、右两部分，其中左边为有序区，右边为无序区，将无序区中的元素逐个插入到有序区的适当位置中。,设待排序的记录存放在数组,A1.n,中。初始时，,A1,自成,1,个有序区，无序区为,A2.n,。,顺序将无序区中的每一个元素逐一插入到有序区的适当位置，直到无序区中无元素为止。,7.2.1,直接插入排序,7.2,插入排序,具体做法：,(1),设置监视哨或临时变量保存待插入元素,Ai,(,腾出,Ai,空间,),。,(2),将待插入记录,Ai,的关键字从右向左依次与有序区中记录,Aj(j,=i-1,，,i-2,，,，,1),的关键字进行比较：若,Aj.key,Ai.key,，则将,Aj,后移一个位置；若,Aj.key,=,Ai.key,，则查找过程结束，,j+1,即为,Ai,的插入位置。,7.2.1,直接插入排序,7.2,插入排序,方法一：无监视哨,(,用临时变量保存待插元素,),void,insert_sort(int,A,int,n),int,i,j,temp;,for(i,=2;itemp&j0)/,搜索适当位置,Aj+1=,Aj,;j=j-1;,Aj+1=temp;/,插入,7.2.1,直接插入排序,7.2,插入排序,方法二：设监视哨,(A0,作监视哨,),void,insert_sort(int,A,int,n),int,i,j;,for(i,=2;iA0)/,搜索适当位置,Aj+1=,Aj,;j=j-1;,Aj+1=A0;/,插入,7.2.1,直接插入排序,7.2,插入排序,7.2.1,直接插入排序,待排元素序列：,53 27 36 15 42,42,第一次排序：,27 27 53 36 15 42,42,第二次排序：,36 27 36 53 15 42,42,第三次排序：,15 15 27 36 53 42,42,第四次排序：,42 15 27 36 42 53,42,第五次排序：,42,15 27 36 42,42,53,示例：,7.2,插入排序,性能分析：,1、稳定性：在搜索插入位是遇到相等元素就停止，所以是稳定的。,2、空间性能：仅用了一个辅助单元。,3、时间性能：循环,n-1,次，每次循环的基本操作是比较和移动元素，其总次数取决于待排序列初始特性。,最好情况为,O(n,),，最坏情况为,O(n,2,),。,7.2.1,直接插入排序,7.2,插入排序,将待排序列分为若干组，在每组内进行直接插入排序，以使整个序列基本有序，然后再对整个序列进行直接插入排序。,7.2.2,希尔排序,先取一个小于,n,的整数,d,1,作为第一个增量，把文件的全部记录分成,d,1,个组,所有距离为,d,1,的倍数的记录放在同一个组中。先在各组内进行直接插人排序,然后，取第二个增量,d,2,=1)/,通过步长，逐次重复排序,for(i,=dh+1;i0&temp,Aj,-dh)/,查找插入位,Aj,=,Aj,-dh;j=j-dh;,Aj,=temp;/,插入,dh=dh/2;/,取下一步长,7.2.2,希尔排序,7.2,插入排序,7.2.2,希尔排序,d1=5,一趟排序结果,d2=3,二趟排序结果,d3=1,三趟排序结果,100,60,80,70,20,14,19,19,55,32,33,14,100,33,19,19,32,20,60,80,70,55,14,32,19,19,20,33,60,80,70,55,100,14,19,19,32,20,33,60,80,70,55,100,14,19,19,32,20,33,60,80,70,55,100,14,19,19,20,32,33,55,60,80,100,70,示例：,7.2,插入排序,性能分析：,7.2.2,希尔排序,希尔排序时间性能分析很难，关键字的比较次数与记录移动次数依赖于步长因子序列的选取。考虑到每一趟都是在上一趟的基础上进行，可认为是基本有序，所以各趟的时间复杂度为,O(n,),，按每次取步长的一半的方式进行，需要,log,2,n,趟，所以总的时间复杂度为,O(nlog,2,n),。,希尔排序方法是一个不稳定的排序方法。,7.3,交换排序,两两比较待排序的元素，若倒序则交换。,基本思想,通过对待排序序列从后向前,(,从下标较大的元素开始,),，依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部,(,从下标较大的单元移向下标较小的单元,),，就象水底下的气泡一样逐渐向上冒。,7.3.1,冒泡排序,7.3,交换排序,排序过程：,（,1,）初始：,A1.n,为无序区。,（,2,）第,i,趟扫描时，,A1.i-1,和,Ai.n,分别为当前的有序区和无序区,扫描仍是从无序区底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置,Ai,上，结果是,A1.i,变为新的有序区。,7.3.1,冒泡排序,排序过程可设置交换标志，在每趟排序结束时对其进行判断，作为是否继续的条件，以提高算法的性能。,7.3,交换排序,方法一：不设置交换标志,void,bubble_sort(int,A,int,n),int,i,j,temp;,for(i,=1;i=i+1;j-)/,从后往前逐个比较,if(Aj,Aj-1)/,倒序时交换,temp=,Aj,;,Aj,=Aj-1;Aj-1=temp;,7.3.1,冒泡排序,分析：,各趟的比较次数依次为,n-1,、,n-2,、,、,2,、,1,，所以时间复杂度为,O(n,2,),。,7.3,交换排序,方法二：设置交换标志,void,bubble_sort(int,A,int,n),int,i,j,temp,flag=1;/flag,是交换标志，交换为,1,。,for(i,=1;i=i+1;j-)/,从后往前逐个比较,if(Aj,Aj-1)/,倒序时交换,temp=,Aj,;,Aj,=Aj-1;Aj-1=temp;flag=1;,7.3.1,冒泡排序,7.3,交换排序,7.3.1,冒泡排序,20,35,18,12,49,12,18,20,35,49,12,20,18,35,49,12,20,18,35,49,初始序列,第一趟,第二趟,第三趟，无交换，结束,示例：,7.3,交换排序,算法分析：,1,、时间性能：依赖于待排序序列的初始特性。,最好情况：初始为正序，则仅比较一趟，比较次数为,n-1,，交换次数为,0,，所以时间复杂度为,O(n,),。,最坏情况：初始为逆序，则每一趟的比较和交换次数均达最大值，因而总比较和交换次数为,n(n-1)/2,，所以时间复杂度为,O(n,2,),。,一般情况：设出现各种排列的概率相同，取上述两者的平均值，所以时间复杂度为,O(n,2,),。,2,、该算法是稳定的排序算法，且空间性能为,S(1),。,7.3.1,冒泡排序,7.3,交换排序,任取待排序列中的某个元素作为基准,(,一般取第一个元素,),，通过一趟排序，将待排元素分为左右两个子序列，左子序列元素均小于等于基准元素，右子序列则大于等于基准元素，而基准元素放在这两部分之间作为分界点,(,即得到一个划分,),，然后分别对两个子序列采用相同的方式来划分和排序，直至每个子表仅有一个元素或空表为止。,7.3.2,快速排序,7.3,交换排序,划分方法：,1,、基准元素,(,表第一个元素,),保存到一空间,(,如,x),，以腾出一空位。,2,、从后往前搜索一个比基准元素小的元素并放置前面空位，则腾出后面空位。,3,、从前往后搜索一个比基准元素大的元素并放置后面空位，则腾出前面空位。,4,、重复,2,、,3,，直到两边搜索空位重合，然后将基准元素放在该空位。,7.3.2,快速排序,7.3,交换排序,划分算法：,int,partition(int,a,，,int,s,，,int,t)/,O(n,),int,i=s,，,j=t,；,int,x=,as,；,/i,从左至右，,j,从右至左,while(i!=j)/,直至,i,与,j,相遇为止,while(ix)j-,；,/,找比,x,小的元素,aj,if(ij),ai,=,aj,；,i+,；,/,找到调前面空位,while(ij&,ai,x)i+,；,/,找比,x,大的元素,ai,if(ij),aj,=,ai,；,j-,；,/,找到调后面空位,ai,=x,；,/,基准元素放在最终位,return i,；,/,返回中间元素位,7.3.2,快速排序,7.3,交换排序,7.3.2,快速排序,一次划分过程示例：,初始序列：,基准,x=80,80,，,16,，,100,，,35,，,85,，,20,j,i,20,，,16,，,35,，,35,，,85,，,100,i,j,20,，,16,，,10,，,35,，,85,，,100,j,i,j,i,20,，,16,，,100,，,35,，,85,，,基准,x=80,20,，,16,，,35,，,80,，,85,，,100,一次划分结果,7.3,交换排序,快速排序算法,(,采用递归调用,),：,void,quicksort,(,int,a,，,int,s,，,int,t),int,i,；,if(s,=t)return,；,i=partition(a,，,s,，,t),；,quicksort,(a,，,s,，,i 1),；,quicksort,(a,，,i+1,，,t),；,7.3.2,快速排序,7.3,交换排序,算法分析：,稳定性：不稳定的。,空间性能：快速排序的递归调用在最坏情况下所需的栈空间为,S(n,),，若让左、右区域元素个数较少的先排序，则最坏情况下所需的栈空间为,S(log,2,n),。,时间性能：在,n,个记录的待排序列中，一次划分需要约,n,次关键字比较，时效为,O(n,),，最坏情况：即每次划分，只得到一个子序列，时效为,O(n,2,),；理想情况：每次划分，正好将其分成两个等长的子序列，则为,O(nlog,2,n),7.3.2,快速排序,7.4,选择排序,在每一趟排序中，从待排序子表中选出关键字最小,(,最大,),的元素放在其最终位置上，直到整个序列的元素选完。,基本思想,7.4.1,直接选择排序,第一次从,A1.n,中选取最小值，与,A1,交换，第二次从,A2.n,中选取最小值，与,A2,交换，第,i,次从,Ai.n,中选取最小值，与,Ai-1,交换，,，这样，,n,个记录的文件的直接选择排序可经过,n-1,趟直接选择排序得到有序结果。,7.4,选择排序,算法实现：,void,selectsort,(,int,an,),int,i,，,j,，,min,，,t,；,for(i=0,；,in-1,；,i+),min=i,；,for(j,=i+1,；,jn,；,j+),if(ai,amin,)min=j,；,if(min,!=i)t=,ai,；,ai,=,amin,；,amin,=t,；,7.4.