《数据结构》第10章：排序.ppt

王钢王钢 主编主编清华大学出版社清华大学出版社第10章排序l排序的基本概念l常用内部排序l外部排序直接插入排序直接插入排序是插入排序中最简单的排序方法，假设排序表中有n个记录，存储在一维数组Rn中。直接插入排序的基本思想为：把待排记录按排序码大小插入到已排好序的有序表中。算法10.1直接插入排序算法voidD_InsertSort(ElemtypeR,intn)/对记录序列R1.n作直接插入排序inti;for(i=2;i=n;+i)if(Ri.keyRi-1.key)/小于时，需要Ri-1插入有序表适当位置R0=Ri;/复制为监视哨for(j=i-1;R0.keyRj.key;-j)Rj+1=Rj;/记录后移Rj+1=R0;/插入到正确位置例例10.1设一组关键码为8,3,2,5,9,1,6，按递增的顺序进行排序，则基本过程如图10.1所示：图10.1直接插入排序的过程直接插入排序的算法分析，实现排序的基本操作有两个：(1)比较。(2)移动记录。折半插入排序折半插入排序的基本方法是：用二分查找法将待插入记录在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入。算法10.2折半查找算法描述voidB_InsertionSort(ElemtypeR,intn)/对记录序列R1.n作折半插入排序inti,low,high,mid;for(i=2;in;+i)R0=Ri;/将Ri暂存到R0low=1;high=n-1;while(low=high)/在Rlow.high序列中寻找折半查找插入的位置m=(low+high)/2;/折半if(R0.key=high+1;-j)/high+1为插入位置Rj+1=Rj;/记录后移Rhigh+1=R0;/插入记录希尔排序(又称缩小增量排序)l希尔排序(Shellssort)又称缩小增量排序，是1959年由D.L.Shell提出来的。希尔排序可以理解为对直接插入排序的一种改进。直接插入排序是从第二个元素开始比较的，循环起始条件为i=2，可以将i=2写成i=1+1，将第一个1用dk代替，即循环初始条件为i=dk+1，dk是一个希尔增量序列，一般可取做dk=5,3,1(当然也可以取其他素数序列，但最后一个必为1)，从第i个记录开始，间隔dk的记录为一组，每次用第i个关键字与第Idk个关键字进行比较后做插入排序。例例10.2已知排序表关键字序列为：49,38,65,97,76,13,27,49,55,04,则希尔排序的排序过程如图10.2所示。算法10.3希尔排序算法voidShellInsert(ElemtypeR,intdk)/对R1.n进行一趟插入排序，dk为步长因子inti,j;for(i=dk+1;i=n;i+)/小于1时需将Ri插入有序表if(Ri.key0&R0.keyRj.key;j=j-dk)Rj+dk=Rj;/记录后移Rj+dk=R0;/插入到正确位置voidShellSort(DataTypeR,intn,intd,intt)/按增量序列0，1.t-1对顺序表R1.n作希尔排序for(k=0;kt;k+)ShellInsert(R,dk);一趟增量为dk的插入记录冒泡排序l冒泡排序的基本思想：从第一个元素开始，通过每两个相邻元素的比较，大的记录下沉(后移)，同时较小的记录就像“气泡”一样浮到序列前面的位置。一趟冒泡排序后，值最大的记录就排在了序列的最后，二趟排序后，第二大的记录就排在了倒数第二个位置，依此类推，直到把整个记录排完为止，序列就变成有序的了。l需要把每一趟冒泡排序最后一个下沉记录的位置记下，下一遍只检查比较到此为止，到所有记录都不发生下沉时，整个过程结束。所以n个元素实施冒泡排序，共需要n1趟排序，每趟需要ni次比较。算法10.4冒泡排序的基本算法voidBubble_Sort(ElemtypeR,intn)inti,j,flag;for(i=1;in;i+)/共进行n-1趟比较flag=0;for(j=1;jRj+1.key)R0=Rj;/R0作为交换的中间变量Rj=Rj+1;Rj+1=R0;flag=1;if(flag=0)return;/若第一趟过后，没有发生交换，则结束循环快速排序l快速排序是对冒泡排序的一种改进。找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列以该记录关键字为枢轴分割成两部分：枢轴元素左边的所有的关键字值均小于枢轴元素，枢轴元素右边的所有元素值均大于枢轴元素。第二趟再分别对分割成两部分的子序列进行快速排序，依此类推，直到每个待排序列的子序列中只有一个记录时为止，整个排序过程结束。例例10.3对关键码序列43,60,54,17,73,3,1,55实施一趟快速排序，其排序过程如图10.3所示。算法10.5快速排序一次划分算法的描述intPartition(ElemtypeR,intlow,inthigh)/交换记录子序列Rlow.high中的记录，使枢轴记录到位，并返回其所/在位置，此时，在它之前(后)的记录均不大(小)于它R0.key=Rlow.key;/用子表的第一个记录作枢轴记录privotkey=Rlow.key;while(lowhigh)/从表的两端交替地向中间扫描while(low=pivotkey)-high;if(lowhigh)/将比枢轴记录小的记录交换到低端Rlow=Rhigh;low+;while(lowhigh&Rlow.key=pivotkey)+low;if(lowhigh)/将比枢轴记录大的记录交换到高端Rhigh=Rlow;high-;Rlow=R0;/将比枢轴记录到位returnlow;/返回枢轴所在位置/Partition算法10.6快速排序的算法描述voidQSort(ElemtypeR,ints,intt)/对记录序列Rs.t进行快速排序if(st)/长度大于1i=Partition(R,s,t);/将Rs.t一分为二QSort(R,s,i-1);/对低子表递归排序，i是枢轴位置QSort(R,i+1,t);/对高子表递归排序voidQuickSort(ElemtypeR,intn)/对记录序列进行快速排序QSort(R,1,n);简单选择排序l简单选择排序是最简单的一种选择排序。其基本思想是：对有n条记录的关键字序列，第i趟简单选择排序是从关键字序列中第i个记录开始到第n个记录结束的ni+1个记录中选出关键字最小的记录与第i个记录进行交换。(其中i从1到n1共进行n1趟选择排序)例例10.4对数据序列54,32,48,32,60,7,18,40进行简单选择排序，其过程如图10.4所示。图10.4简单选择排序的过程算法10.7简单选择排序算法voidSelect_Sort(ElemtypeR,intn)inti,j,k;for(i=1;in;i+)/做n-1趟选取for(k=i,j=i+1;j=n;j+)/在i开始的n-i+1个记录中选关键字最小的记录if(Rj.keyRk.key)k=j;/k中存放关键字最小的记录的下标if(i!=k)R0=Rk;Rk=Ri;Ri=R0;/交换记录树形选择排序l树形选择排序又称为锦标赛排序，其基本思想是：首先对n个记录的关键字进行两两比较，选出最大的作为子树的根结点。然后在其中n/2个较大的根结点之间再进行两两比较，直到选出最大关键字的记录为止，可以用一棵有n个叶子结点的完全二叉树表示。此时根结点就是排序关键字最大的结点，把选走后的叶设为最小，重新进行比较选择，依此选择下去，直到排序完成。堆排序l设有n个元素的序列k1,k2,kn，当且仅当待排序列关键字满足下述关系之一时，称之为堆堆。如图10.7所示分别为小顶堆和大顶堆的表示和存储结构。(a)堆顶元素取最大值(b)堆顶元素取最小值图10.7堆的示意图例例10.5对关键码序列16,24,53,47,36,85,30,91构造的堆树如图10.8所示。(a)初始序列完全二叉树(b)从第4个结点开始调整(c)从第3个结点开始调整(d)从第2个结点开始调整(e)整棵树调整为堆图10.8堆调整示意图算法10.8筛选的算法voidHeapAdjust(ElemtypeR,ints,intm)/已知Rs.t中记录的关键字除Rs之外均满足堆的定义，/本函数调整Rs的关键字，使Rs.m成为一个大顶堆(对其中记录的关键字而言)inti,j;Elemtyperc;rc=Rs;for(j=2*i;j=t;j*=2)/沿key较大的孩子结点向下筛选if(jm&Rj.key=Rj.key)break;/不用调到叶子就到位了Ri=Rj;i=j;/准备继续向下调整Ri=rc;/插入算法10.9堆排序的基本算法voidHeapSort(ElemR,intn)/对记录序列R1.n进行堆排序inti;for(i=n/2;i0;-i)/把R1.n建成大顶堆HeapAdjust(R,i,n);for(i=n;i1;-i)R0=Ri;/将堆顶记录和当前未经排序子序列R1.i中最后一个记录相互交换R1=Ri;Ri=R0;HeapAdjust(R,1,i-1);/将R1.i-1重新调整为大顶堆/HeapSort归并排序所谓归并排序归并排序就是两个或者两个以上的有序数据序列合并成一个有序序列的过程。归并排序的基本思想为：(1)将n个记录的待排序列看成为有n个长度都为1的有序表；(2)将两两相邻的子表归并为一个有序子表；(3)重复上述步骤，直至归并为一个长度为n的有序表。例例10.6对下述关键字15,13,21,25,24,10,12,11实施归并排序，其基本过程如图10.9所示。图10.9归并排序的排序过程算法10.10一趟归并排序具体算法voidMergePass(ElemtypeR，ElemtypeR1,intlen,intn)/len是本趟归并中有序表的长度，从R1.n归并到R11.n中inti；for(i=1;i+2*len-1=n;i=i+2*len)/对两个长度为len的有序表的合并Merge(R，R1，i,i+len-1，n)；/归并长度为len的两个相邻子文件if(i+len-1n)Merge(R，i，i+len-1，n)；/一组半的情况Elseif(i=n)While(i=n)/最后一组没有合并者R1i+=Ri+;算法10.112-路归并排序迭代算法voidMergeSort(ElemtypeR,intn)/采用自底向上的方法，对R1.n进行二路归并排序intlen=1；while(lenn)MergePass(R,R1,len)；len*=2;MergePass(R1,R,len)；算法10.122-路归并的递归算法voidMsort(ElemtypeR,ElemtypeR1,ints,intt)/将Rs.t归并排序为R1s.tintm;if(s=t)R1s=Rs;Elsem=(s+t)/2;/平分*p表Msort(R,R1,s,m);/递归的将Rs.m归并为有序的R1s.mMsort(R,R1,m+1,t);/递归的将Rm+1.t归并为有序的R1m+1.tMerge(R1,R,s,m,t);voidMergeSort(ElemtypeR,R1intn)/对顺序表R作归并排序Msort(R,R1,1,n);基数排序l多关键字的排序l链式基数排序链式基数排序l例例10.7以静态链表存储的排序表的基数排序过程如图10.10所示。排序表记录关键字为：178,109,63,593,284,55,269,8,830，如图10.10为分配和收集的过程。相关的数据结构：相关的数据结构：#defineKEY_NUM8/关键字项数#defineRADIX10/关键字基数，此时为十进制整数的基数#defineMAX_SPACE1000/分配的最大可利用存储空间typedefstructKeyTypekeysKEY_NUM;/关键字字段InfoTypeotheritems;/其他字段intnext;/指针字段NodeType;/静态链表结点类型typedefstructintf;inte;Q_Node;typedefQ_NodeQueueRADIX;/各队列的头尾指针基数排序算法voidDistribute(NodeTypeR,inti,Queueq)/分配算法：静态链表中R中的记录已按key0,key1,keyi-1有序/本算法按第i个关键字keyi建立RADIX个子表，使同一子表中的记录keyi相同，/qi.f和qi.e分别指向第i个子表的第一个和最后一个记录intj,p;for(j=0;jRADIX;j+)/各子表初始化为空表qj.f=qj.e=0;for(p=R0.next;p;p=Rp.next)j=ord(Rp.keysi);/ord将记录中第i个关键字影射到0RADIX-1if(!fj)qj.f=p;elseRqj.e.next=p;qj.e=p;/将p所指的结点插入到第j个队列中voidCollect(NodeTypeR,inti,Queueq)/收集算法：本算法按q0qRADIX-1所指各子表依次链接成一个链表intj;for(j=0;!qj.f;j=succ(j);/找第一个非空子表，succ为求后继函数R0.next=qj.f;t=qj.e;/R0.next指向第一个非空子表中第一个结点While(jRADIX)for(j=succ(j);jRADIX-1&!qj.f;j=succ(j);/找下一个非空子表if(qj.f)Rt.next=qj.f;t=qj.e;/链接两个非空子表Rt.next=0;/t指向最后一个非空子表中的最后一个结点voidRadixSort(NodeTypeR,intn)/对R作基数排序，使其成为按关键字升序的静态链表，R0为头结点inti;Queueq;/定义队列for(i=0;in;i+)Ri.next=i+1;Rn.next=0;/将R改为静态链表for(i=0；iKEY_NUM;i+)/按最低位优先依次对各关键字进行分配和收集Distribute(R,i,q);/第i趟分配Collect(R,i,q);/第i趟收集外部排序l外部排序外部排序指的是大文件的排序，即待排的记录存储在外存储器上，在排序过程中需要进行多次的内、外存之间的交换，外部排序基本上由两个相对独立的阶段组成。首先，按可用内存的大小，将外存上含有n个记录的文件分成若干个长度为k的子文件或段，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入内存。通常称这些有序子文件为归并段或顺串；然后，对这些归并段进行逐趟归并，使归并段(有序子文件)逐渐由小到大，直至得到整个有序文件为止。算法10.13k-路归并算法typedefintLoserTree(k);/败者树是完全二叉树且不含叶子，可采用顺序存储结构typedefstructKeyTypekey;ExNOde,Externalk;/外结点，只存放待归并记录的关键字viodK_Merge(LoserTree*ls,Externa*b)/k-路归并处理程序，利用败者树ls将编号从0到k-1的k个输入归并段中的记录归并到输出归并段，b0到bk-1为败者树上的k个叶子结点，分别存放k个输入归并段中当前记录的关键字inti;LoseTreeq;for(i=0;i0)if(bs.keyblst.keyslst;/s指示新的胜者t=t/2;ls0=s;voidCreateLoserTree(LoseTree*ls)/建立败者树，已知b0到bk-1为完全二叉树ls的叶子结点存有k个关键字/沿从叶子到根的k条路径将ls调整为败者树inti;bk.key=MINKEY;/设MINKEY为关键字可能的最小值for(i=0;i0;i-)Adjust(ls,i);/依次从bk-1,bk-2,b0出发调整败者