天津科技大学数据结构-排序PPT课件

第十章排序概述插入排序交换排序选择排序归并排序分配排序外排序排序是计算机中经常遇到的操作。,第十章排序10.1概述排序计算机内经常进行的一种操作，将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97,一般，假设含n个记录的序列为R1,R2,，Rn其相应的关键字序列为K1,K2,，Kn这些关键字相互间可以进行比较，即它们之间存在一个关系Kp1Kp2Kpn按此固有关系将原记录序列重新排列为Rp1,Rp2,，Rpn的操作称作排序。排序算法的稳定性判断标准：关键字相同的数据对象在排序过程中是否保持前后次序不变。如2,2*,1，排序后若为1,2*,2，则该排序方法是不稳定的。,内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。,使有序区中记录的数目增加一个或几个的操作称为一趟排序。,逐步扩大记录有序序列长度的方法大致有下列几类：插入类将无序序列中的一个或几个记录“插入”到有序序列中；交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加到有序子序列中;选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中;归并类通过“归并”两个或两个以上的记录有序序列;其它方法,10.2插入排序假设在排序过程中，记录序列R1.n的状态为：,则一趟直接插入排序的基本思想：将记录Ri插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1变为R1.i。完成一趟“插入”需分三步进行：1查找Ri的插入位置j+1；2将Rj+1.i-1中的记录后移一个位置；3将Ri复制到Rj+1的位置上。,一、直接插入排序利用顺序查找实现“在R1.i-1中查找Ri的插入位置”的插入排序。直接插入排序算法的三个要点：1、从Ri-1起向前顺序查找，监视哨设置在R0；R0=Ri;/设置“哨兵”for(j=i-1;R0.keyRj.key;-j);/从后往前找/循环结束后，可得Ri的插入位置j+12在查找过程中找到的关键字大于R0.key的记录需在查找的同时向后移动；for(j=i-1;R0.keyRj.key;-j)Rj+1=Rj;3i=2，3，,n,实现整个序列的排序。,算法描述如下:voidInsertionSort(ElemR,intn)/对记录序列R1.n作直接插入排序。for(i=2;i=n;+i)R0=Ri;/复制为监视哨for(j=i-1;R0.keya1while(SLk.key=SLi.key)j=k,k=SLk.next;SLj.next=i;SLi.next=k;/LinsertionSort,voidArrange(ElemSL,intn)p=SL0.next;/p=6for(i=1;in;+i)while(p=temp.key),QUICKSORT(rectypeR,ints1,intt1)inti;if(s1t1)i=PARTITION(R,s1,t1);QUICKSORT(R,s1,i-1);QUICKSORT(R,i+1,t1);,最好情况每次所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左右两个无序子区的长度大致相等。,快速排序的时间复杂度考虑关键字的比较次数和对象移动次数最坏情况每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准的左边(或右边)为空，划分前后无序区的元素个数减少一个，因此，排序必须做n-1趟，每一趟中需做n-i次比较，所以最大比较次数为,设C(n)表示对长度为n的序列进行快速排序所需的比较次数，显然，它应该等于对长度为n的无序区进行划分所需的比较次数n-1，加上递归地对划分所得的左右两个无序子区进行快速排序所需的比较次数。假设文件长度n=2k，k=log2n，因此有：,快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为O(n2)；最好时间复杂度为O(nlog2n)。可证:快速排序的平均时间复杂度也是O(nlog2n)。快速排序是不稳定的排序方法。,四、选择排序基本原理将待排序的结点分为已排序(初始为空)和为未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。两种常见的选择排序直接选择排序堆排序,直接选择排序的基本过程在一组对象Vi到Vn-1中选择具有最小关键字的对象若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调。删除具有最小关键字的对象，在剩下的对象中重复第(1)、(2)步，直到剩余对象只有一个为止。,49,38,65,97,76,13,27,49,13,38,65,97,76,49,27,49,13,27,65,97,76,49,38,49,13,27,38,97,76,49,65,49,13,27,38,49,76,97,65,49,13,27,38,49,49,97,65,76,13,27,38,49,49,65,97,76,13,27,38,49,49,65,76,97,直接选择排序示例,直接选择排序算法SELECTSORT(rectypeR)inti,j,k;rectypetemp;for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+)if(Rj.keylow(n/2)的结点都是叶子，因此，以这些结点为根的子树都已是堆。即只需依次将序号为low(n/2)，low(n/2)-1，.，1的结点作为根的子树都调整为堆即可。以大根堆为例进行说明“筛选法”基本思想：因为Ri的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的结点，所以在Ri和它的左右孩子中选取关键字最大的结点放到Ri的位置上。,若Ri的关键字已是三者中的最大者，则无须做任何调整，以Ri为根的子树已构成堆，否则，将Ri和具有最大关键字的左孩子R2i或右孩子R2i+1进行交换。假定R2i的关键字最大，将Ri和R2i交换位置，交换之后有可能导致R2i为根的子树不再是堆，但由于R2i的左右子树仍然是堆，于是可以重复上述过程，将以R2i为根的子树调整为堆，.，如此逐层递推下去，最多可能调整到树叶。,例子：关键字序列为42，13，91，23，24，16，05，88，n=8，故从第四个结点开始调整,42,13,91,23,24,16,05,88,42,13,91,23,24,16,05,88,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,不调整,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,42,88,91,23,24,16,05,13,42,88,91,23,24,16,05,13,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,建成的堆,筛选算法SIFT(rectypeR,inti;intm)intj;rectypetemp;temp=Ri;j=2*i;while(j=1;i-)SIFT(R,i,n);for(i=n;i=1;i-)temp=R1;R1=Ri;Ri=temp;SIFT(R,1,i-1);,堆排序的时间复杂度堆排序的时间复杂性为O(nlog2n)空间复杂性为O(1)堆排序是不稳定的排序方法。,五、归并排序通过对两个有序结点序列的合并来实现排序。归并：将若干个已排好序的部分合并成一个有序的部分。归并的基本思想将待排序列R0到Rn-1看成n个长度为1的有序子序列，把这些子序列两两归并，便得到high(n/2)个有序的子序列。然后再把这high(n/2)个有序的子序列两两归并，如此反复，直到最后得到一个长度为n的有序序列。该归并操作，都是将两个子序列归并为一个子序列，称“二路归并”，类似地还有“三路归并”或“多路归并”。,归并过程示例,(25)(57)(48)(37)(12)(92)(86),(2557)(3748)(1292)(86),(25374857)(128692),(12253748578692),一趟归并算法MERGEPASS(rectypeR,rectypeR1,intlength)inti,j;i=0;while(i+2*length-1n)MERGE(R,R1,i,i+length-1,i+2*length-1);i=i+2*length;if(i+length-1n-1)MERGE(R,R1,i,i+length-1,n-1);elsefor(j=i;jn;j+)R1j=Rj;,归并算法MERGE(rectyprR,rectypeR1,intlow,intmid,inthigh)inti,j,k;i=low;j=mid+1;k=low;while(i=mid),归并排序算法MERGESORT(rectypeR)intlength=1;while(lengthn)MERGEPASS(R,R1,length);length=2*length;MERGEPASS(R1,R,length);length=2*length;,算法复杂性分析归并排序在第i趟归并后，有序子文件长度为2i，因此，因此，对于具有n个记录的序列来说，必须做high(log2n)趟归并，每趟归并所花的时间为O(n)。所以，二路归并排序算法的时间复杂度为O(nlog2n)，辅助数组所需的空间为O(n)。归并排序是稳定的排序方法。,六、基数排序基本原理，采用“分配”和“收集”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。下面先介绍多关键字排序多关键字排序方法示例如对扑克牌的排序每张扑克牌有两个“关键字”：花色和面值它们之间有次序的优先。对以上排序，可以先对花色排序，或先对面值排序。,多关键字有序的概念考虑对象序列V0,V1,.,Vn-1，每个对象Vi含d个关键字(Ki1,Ki2,.,Kid)。若对序列中的任意两个对象Vi和Vj都有(Ki1,Ki2,.,Kid)=0;j-)for(i=0;im;i+)Bi.f=-1;Bi.e=-1;while(p!=-1)k=Rp.keyj;if(Bk.f=-1)Bk.f=p;elseRBk.e.next=p;Bk.e=p;p=Rp.next;i=0;while(Bi.f=-1)i+;t=Bi.e;p=Bi.f;while(im-1)i+;if(Bi.f!=-1)Rt.next=Bi.f;t=Bi.e;Rt.next=-1;returnp;,intRADIXSORT(r