数据结构6排序

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,6,排序,1,主要内容,排序的基本概念,简单排序方法,选择排序,插入排序,起泡排序,先进排序方法,快速排序,归并排序,基数排序,2,6.1,排序的基本概念,排序是计算机内经常进行的一种操作，其目的是将一组,“无序”的记录序列调整为“有序”,的记录序列。,例如：,将下列关键字序列,52, 49, 80, 36, 14, 58, 61, 23, 97, 75,调整为,14, 23, 36, 49, 52, 58, 61 ,75, 80, 97,定义,假设含,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,的操作称作排序。,3,6.1,排序的基本概念,typedef,int,KeyType; /,关健字类型为整数,typedef,struct ,KeyType key;,/,关键字项,infoType OtherInfo; /,其它信息,RcdType;,/,记录类型,4,6.1,排序的基本概念,排序分类,按待排序记录所在位置,内部排序：待排序记录存放在内存,外部排序：排序过程中需对外存进行访问的排序,按排序依据原则,插入排序：直接插入排序、折半插入排序、希尔排序,交换排序：冒泡排序、快速排序,选择排序：简单选择排序、堆排序,归并排序：,2-,路归并排序,基数排序,排序稳定性,5,6.1,排序的基本概念,按排序所需工作量,简单的排序方法：,T(n)=O(n,),先进的排序方法：,T(n)=O(nlogn),基数排序：,T(n)=O(d.n),排序基本操作,比较两个关键字大小,将记录从一个位置移动到另一个位置,r,2,r,i-1,r,i,r,i+1,r,1,r,n,有序序列,R1.i-1,无序序列,Ri.n,有序序列,R1 . i,无序序列,Ri+1 . n,排序算法的思想,:,将待排序列看成是看成是有有序序列和无序序列组成，每次排序都会按照某种原则将无序序列中的某个元素取出，放在有序序列中，这样经,n-1,次操作就会将无序序列,R1.n,排成有序序列,内部排序的过程是一个,逐步扩大,记录的,有序序列长度,的过程。,6,基于不同的“,扩大,”,有序序列长度的,方法，内部排序方法,大致可分下列几种类型：,插入类,交换类,选择类,归并类,其它方法,6.1,排序的基本概念,7,6.1,排序的基本概念,插入类排序,将无序子序列中的一个或几个记录,“,插入,”,到有序序列中，从而增加记录的有序子序列的长度。,交换类排序,通过,“,交换,”,无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,选择类排序,从记录的无序子序列中,“,选择,”,关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,归并类排序,通过,“,归并,”,两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。,其它类排序,8,6.2,插入排序,6.2.1,直接插入排序,6.2.2,二分,(,折半）插入排序,6.2.3,希尔排序,9,6.2.1,直接插入排序,插入排序过程：,整个排序过程为,n-1,趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序,有序序列,R1.i-1,Ri,无序序列,Ri.n,有序序列,R1.i,无序序列,Ri+1.n,10,49 38 65 97 76 13 27,i=2,38,(38 49) 65 97 76 13 27,i=3,65,(38 49 65) 97 76 13 27,i=4,97,(38 49 65 97) 76 13 27,i=5,76,(38 49 65 76 97) 13 27,i=6,13,(13 38 49 65 76 97) 27,i=1 ( ),i=7 (13 38 49 65 76 97) 27,27,j,j,j,j,j,j,97,76,65,49,38,27,(13 27 38 49 65 76 97),排序结果：,例：,(,49 38 65 97 76 13 27),思考：寻找插入位置时，应该从后向前找还是从前向后找？为什么？,11,算法名：,InsertSort,1.,输入：无序数组,R,2.,输出：有序数组,R,3.,算法,(1).,排序趟数,i=2n,(2),对于每一趟,i,将无序序列的第一个元素,Ri,插入到有序序列,R1i-1,中,InsertSort(R), for(i=2;i=1;j-),if(R0=1 &,(R0Rj),;j-),Rj+1=Rj;,Rj+1=R0;,InsertSort(R), for(i=2;i=n;i+),if(RiRi-1),InsertPass(R,i );,12,算法评价,时间复杂度,若待排序记录按关键字从小到大排列,(,正序,),关键字比较次数：,记录移动次数：,0,若待排序记录按关键字从大到小排列,(,逆序,),关键字比较次数：,记录移动次数：,若待排序记录是随机的，取平均值,关键字比较次数：,记录移动次数：,T(n)=O(n),空间复杂度：,S(n)=O(1),13,6.2.2,二分,(,折半,),插入排序,排序过程：,用二分查找方法确定插入位置的排序叫,例,i=1 (30) 13 70 85 39 42 6 20,i=2,13,(13 30) 70 85 39 42 6 20,i=7,6,(6 13 30 39 42 70 85 ) 20,.,i=8,20,(6 13 30 39 42 70 85 ) 20,s,j,m,i=8,20,(6 13 30 39 42 70 85 ) 20,s,j,m,i=8,20,(6 13 30 39 42 70 85 ) 20,s,j,m,i=8,20,(6 13 30 39 42 70 85 ) 20,s,j,i=8,20,(6 13 20 30 39 42 70 85 ),插入位置为,S,或,j+1,处,14,算法描述,算法评价,与直接插入排序相比： 关键字比较次数减少 记录移动次数不变,时间复杂度：,T(n)=O(n,),空间复杂度：,S(n)=O(1),15,6.2.3,希尔排序,基本思想：,在直接插入排序算法中，如果待排序列已经是按升序有序的，则直接插入排序的时间复杂性是,T(n)=O(n),Shell,排序就是利用这个特点，先将记录进行粗略地分组，使整个序列大致按升序有序，这样最后进行直接插入排序时，时间复杂性,T(n)O(n,),排序过程：,先取一个正整数,d,1,n,，,把所有相隔,d,1,的记录放一组，组内进行直接插入排序；,然后取,d,2,d,1,，,重复上述分组和排序操作；直至,d,i,=1,，,即所有记录放进一个组中排序为止,16,取,d3=1,三趟分组：,13 27 48 55 4 49 38 65 97 76,三趟排序：,4 13 27 38 48 49 55 65 76 97,例 初始：,49 38 65 97 76 13 27 48 55 4,一趟排序：,13,27,48,55,4,49,38,65,97,76,二趟排序：,13,4,48,38,27,49,55,65,97,76,取,d1=5,一趟分组：,49,38,65,97,76,13,27,48,55,4,取,d2=3,二趟分组：,13,27,48,55,4,49,38,65,97,76,17,ShellInsert(int R ,int dk)/,一次增量排序,for(i=dk+1;i=n;i+),if(Ri0 j-=dk),Rj+dk=Rj;,Rj+dk=R0;,ShellSort(int R , int d,int t)/,一次增量排序,for(k=0; kr2.key,，,则交换；然后比较第二个记录与第三个记录；依次类推，直至第,n-1,个记录和第,n,个记录比较为止,第一趟冒泡排序,，结果关键字最大的记录被安置在最后一个记录上,对前,n-1,个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第,n-1,个记录位置,重复上述过程，直到,“,在一趟排序过程中没有进行过交换记录的操作,”,为止,21,49 38 65 97 76 13 27 30,初始关键字,38 49 65 76 13 27 30,97,第一趟,38 49 65 13 27 30,76,第二趟,38 49 13 27 30,65,第三趟,38 13 27 30,49,第四趟,13 27 30,38,第五趟,13 27,30,第六趟,for(j=1;,jRj+1),/,交换,Rj,和,Rj+1,w=Rj;,Rj=Rj+1;,Rj+1=w;,BulleSort(R),for(i=n; i1; i-), for(j=1;,jRj+1),/,交换,Rj,和,Rj+1,w=Rj;,Rj=Rj+1;,Rj+1=w;,22,算法评价,时间复杂度,最好情况（正序）,比较次数：,n-1,移动次数：0,最坏情况（逆序）,比较次数：,移动次数：,空间复杂度：,S(n)=O(1),T(n)=O(n),23,6.3.2,快速排序方法,基本思想：,首先对无序的记录序列进行,“,一次划分,”,，之后分别对分割所得两个子序列,“,递归,”,进行划分。,无 序 的 记 录 序 列,无序记录子序列,(1),无序子序列,(2),枢轴,一次划分,分别进行划分,24,记录划分：,找一个记录，,以它的关键字作为,“枢轴”,，,凡其,关键字小于枢轴,的记录均,移动至该记录之前，,反之，凡,关键字大于枢轴,的记录均,移动至该记录之后,。,划分过程：对,rs,t,中记录进行一,次划分,，附设两个指针,low,和,high,，,设枢轴记录,r,p,=rs,，,pivotkey=r,p,.key,初始时令,low=s, high=t,首先从,high,所指位置向前搜索第一个关键字小于,pivotkey,的记录，并和,r,p,交换,再从,low,所指位置起向后搜索，找到第一个关键字大于,pivotkey,的记录，和,rp,交换,重复上述两步，直至,low=high,为止,25,s,t,low,high,设,Pivotkey=Rs=52,为枢轴关键字,high,23,low,80,high,14,low,52,Rs=,52,low,high,high,high,low,原序列：,52, 49,80, 36,14, 58, 61, 97,23, 75,一次划分后：,23, 49,14, 36,(52),58, 61, 97,80, 75,26,递归排序,对于上次划分所形成的每个子序列重复进行划分,52, 49,80, 36,14, 58, 61, 97,23, 75,(52),23, 49,14, 36,58, 61, 97,80, 75,14,(23), 49, 36,(58), 61, 97, 80, 75,36,(49),(61), 97, 80, 75,(36),75, 80,(97),(75),80,(80),14, 23, 36, 49, 52, 58, 61, 75, 80, 97,(14),27,算法评价,时间复杂度,最好情况（每次总是选到中间值作枢轴）,T(n)=O(nlog,2,n),最坏情况（每次总是选到最小或最大元素作枢轴）,T(n)=O(n,),空间复杂度：需栈空间以实现递归,最坏情况：,S(n)=O(n),一般情况：,S(n)=O(log,2,n),28,6.4,选择排序,6.4.1,简单选择排序,6.4.2,堆排序,29,6.4.1,简单选择排序,有序序列,R1.i-1,无序序列,Ri.n,Rk,找最小值,Rk,Ri,有序序列,R1.i-1,无序序列,Ri.n,Ri,Rk,Rk,与,Ri,交换,30,选择排序的基本思想：整个排序过程为,n,趟,扫描,，即,首,先,在,n,个记录中选择关键字最小的放在有序子序列的第一个记录位置，然后从剩下的,n-1,个记录中选择关键字最小的,记录,放在有序子序列的第二个记录位置，重复此过程，直到最后一个记录,例：（,49,1,38,65,49,2,76,13,27,52,）,49,1,38,65,49,2,76,13,27,52,13,38,65,49,2,76,49,1,27,52,13,27,65,49,2,76,49,1,38,52,13,27,38,49,2,76,49,1,65,52,13,27,38,49,2,76,49,1,65,52,13,27,38,49,2,49,1,76,65,52,13,27,38,49,2,49,1,52,65,76,13,27,38,49,2,49,1,52,65,76,31,初始：, 49 38 65 97 76 13 27 ,k,j,j,j,j,j,j,k,k,i=1,13,49,一趟：,13,38 65 97 76 49 27 ,i=2,k,k,j,j,j,j,j,27,38,二趟：,13,27,65 97 76 49 38 ,三趟：,13,27,38,97 76 49 65 ,四趟：,13,27,38,49,76 97 65 ,五趟：,13,27,38,49,65,97 76 ,六趟：,13,27,38,49,65,76,97 ,排序结束：,13,27,38,49,65,76,97,32,算法描述,void SelectSort (SqList &L), /,对顺序表,L,作简单选择排序。,RcdType W,；,for (i=1; iL.length; +i),k = i,；,/,选择第,i,小的记录，并交换到位,for (j=i+1; j=L.length; j+ ) /,在,L.ri.L.length,中选择,key,最小的记录,if ( L.rj.key L.rk.key ),k = j,；,if ( i!=k ),W=L.rk,；,L.rk =L.ri,；,L.ri = W,；, /,与第,i,个记录交换, / SelectSort,33,算法评价,时间复杂度,记录移动次数,最好情况：,0,最坏情况：3(,n-1),比较次数：,空间复杂度：,S(n)=O(1),T(n)=O(n),简单选择排序,34,6.4.2,堆排序,35,6.5,归并排序,基本思想：将两个有序表合并成一个有序表的时间复杂性是,T(n)=O(n),关键：将两个有序表合并成一个有序表的算法,3 8 12 15 18,2 5 14,i,j,Rst s=1, t=8, m=5,i=s; j=m+1; k=s;,while( ), if (SRi=SRj), TRk=SRi; i+;,else, TRk=SRj; j+ ;,k+;,while (i=m) TRk+ = SRi+;,while (j=n) TRk+ = SRj+;,i=m & j=t,void Merge(SR,TR,s,m,t),36,问题：实际被排序的序列不可能是有序的,如果无序序列,Rs.t,的两部分,Rs,(s+t)/2,和,R(s+t)/2+1,t,分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。,算法：两类算法,自顶向下,递归算法,自底向上,迭代算法,37,52, 23, 80, 36, 68, 14 (s=1, t=6), 52, 23, 80,36, 68, 14, 52, 23,80, 52, 23, 52,23, 52, 80,36, 68,14,36,68,36, 68,14, 36, 68, 14, 23, 36, 52, 68, 80 ,23,自顶向下的设计方法,递归算法,38,迭代算法,39,利用数组两相邻有序段归并函数，将存于一个数组中的每,len,个元素有序的段分别作两两归并，使数组中的元素每,2*len,个元素有序的函数。,【,算法,】,一趟归并,void mergePass(SR , TR , int n, int len), int i=1, j;,while(i+2*len n) ,merge(SR, TR, i, i+len-1, i+2*len-1);,i+=2*len;,if (i+len =n) /,一个长,len,，另一个不足,len,merge(SR, TR , i, i+len-1, n-1);,40,【,算法,】,迭代的归并排序,假设初始的对象序列有,n,个对象，首先把它看成是,n,个长度为,1,的有序子序列，先做两两归并，得到,n/2,个长度为,2,的归并项（如果,n,为奇数，则最后一个有序子序列的长度为,1,）；再做两两归并，,，如此重复，最后得到一个长度为,n,的有序序列。,void mergeSort(R , TR , n), int len;,len=1;,while(len n),mergePass(R, TR, len);,len*=2;,41,算法评价,:,两种方法,时间复杂度：,T(n)=O(nlog,2,n),空间复杂度：,S(n)=O(n),42,6.6,基数排序,关于排序问题的研究,排序算法是计算机科学的最基本的算法,现在每年仍有排序方面的研究文章出现,主要是基数类的排序算法,理论证明,：基于比较的排序算法，其最坏情况下的时间复杂性极限是,T(n)=O(nlog,2,n),43,6.6.1,桶排序,例,: (5,1, 3,1, 2,1, 2,2, 5,2, 4,1, 4,2, 5,3, 5,4, 2,3, 3,2,),2,3,2,2,2,1,5,4,5,3,5,2,5,1,3,2,3,1,4,2,4,1,(2,1, 2,2, 2,3, 3,1, 3,2, 4,1, 4,2, 5,1, 5,2, 5,3, 5,4,),44,例 对,52,张扑克牌按以下次序排序：,23A,2,3,A,2,3,A23A,两个关键字：花色（,）,面值（,23A,）,并且“花色”地位高于“面值”,多关键字排序思路,最高位优先法（,MSD),：,先对最高位关键字,k1,（,如花色）排序，将序列分成若干子序列，每个子序列有相同的,k1,值；然后让每个子序列对次关键字,k2,（,如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字,kd,排序；最后将所有子序列依次连接在一起成为一个有序序列,6.6.2,基数排序,多关键字,45,最低位优先法,(LSD),：从最低位关键字,kd,起进行排序，然后再对高一位的关键字排序，,依次重复，直至对最高位关键字,k1,排序后，便成为一个有序序列。,MSD,与,LSD,不同特点,按,MSD,排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序,按,LSD,排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序,46,链式基数排序,基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法。,有的逻辑关键字可以看成由若干个关键字复合而成。,例：关键字,K,的,取值,范围为,0,，,999,，则可将,K,看成由,三个关键字（,k0,k1,k2),组成。其中,k0,是百位数，,k1,是十位数，,k2,是个位数。,基数：每,位,关键字的取值,范围。上,例的基为,10,。,链式基数排序：用链表作存储结构的基数排序,47,链式基数排序步骤（设,关键字,K,的,取值,范围为,0,，,999,）,设置,10,个队列，,fi,和,ei,分别为第,i,个队列的头指针和尾指针,第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同,第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表,重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列,48,例,初始状态：,278,109,063,930,589,184,505,269,008,083,109,589,269,278,063,930,083,184,505,008,e0,e1,e2,e3,e4,e5,e6,e7,e8,e9,f0,f1,f2,f3,f4,f5,f6,f7,f8,f9,一趟分配,930,063,083,184,505,278,008,109,589,269,一趟收集：,49,505,008,109,930,063,269,278,083,184,589,二趟收集：,083,184,589,063,505,269,930,e0,e1,e2,e3,e4,e5,e6,e7,e8,e9,f0,f1,f2,f3,f4,f5,f6,f7,f8,f9,二趟分配,008,109,278,930,063,083,184,505,278,008,109,589,269,一趟收集结果：,50,008,063,083,109,184,269,278,505,589,930,三趟收集：,109,008,184,930,e0,e1,e2,e3,e4,e5,e6,e7,e8,e9,f0,f1,f2,f3,f4,f5,f6,f7,f8,f9,三趟分配,063,083,269,278,505,589,505,008,109,930,063,269,278,083,184,589,二趟收集结果：,51,算法描述,算法评价,时间复杂度：,分配：,T(n)=O(n),收集：,T(n)=O(rd),T(n)=O(d(n+rd),其中：,n,记录数,d,关键字数,rd,关键字取值范围,空间复杂度：,S(n)=2rd,个队列指针+,n,个指针域空间,52,初始状态：,1,278,109,063,930,589,184,505,269,008,083,0,2,3,4,5,6,7,8,9,10,f0=0 e0=0,f1=0 e1=0,f2=0 e2=0,f3=0 e3=0,f4=0 e4=0,f5=0 e5=0,f6=0 e6=0,f7=0 e7=0,f8=0 e8=0,f9=0 e9=0,1,1,2,2,3,3,4,4,5,6,6,7,7,8,9,10,4,930,063,083,184,505,278,008,109,589,269,0,3,10,6,7,1,9,2,5,8,53,f0=0 e0=0,f1=0 e1=0,f2=0 e2=0,f3=0 e3=0,f4=0 e4=0,f5=0 e5=0,f6=0 e6=0,f7=0 e7=0,f8=0 e8=0,f9=0 e9=0,1,3,4,4,7,7,9,10,4,930,063,083,184,505,278,008,109,589,269,0,3,10,6,7,1,9,2,5,8,一趟收集：,3,10,1,6,2,5,8,7,505,008,109,930,063,269,278,083,184,589,0,9,2,4,3,8,1,10,6,5,二趟收集：,54,7,505,008,109,930,063,269,278,083,184,589,0,9,2,4,3,8,1,10,6,5,二趟收集：,f0=0 e0=0,f1=0 e1=0,f2=0 e2=0,f3=0 e3=0,f4=0 e4=0,f5=0 e5=0,f6=0 e6=0,f7=0 e7=0,f8=0 e8=0,f9=0 e9=0,4,4,7,9,2,8,7,9,2,8,9,008,063,083,109,184,269,278,505,589,930,0,3,10,2,6,8,1,7,5,4,三趟收集：,3,1,10,6,5,55,