信息奥训班讲义(三)排序.docx

信息奥训班讲义（三）排序排序法一、选择排序se1.ectionsort基本思想：每一步从待排序的数据中选择最小（此处以正序为例，若为反序则正好相反）的数据，依次放在已排好序的子序列的最终，直到全部数据排序完毕。对待排序的记录序列进行11-1遍的处理，第1遍处理是将1.1.n中最小者与1.1.交换位置，第2遍处理是将1.2.n中最小者与U2交换位置，笫i遍处理是将1.i.n中最小者与1.i交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的依次排列好了0初始状态128101462第一步排序281014612其次步排序261014812第三步排序268141012第四步排序268101412第五步排序268101214干脆选择排序的程序如下：ProcedureSort_SeIeCt;VarI,j,k,t:integer;BeginFori:=1ton-1doBeginK:=I;Forj:=i+1.tondoIfakajthenk:=j;Ifk1.thenBegint:=ai;Ai:=ak;k:=t;End：End;End;算法评价：(I)数据比较次数无论数据序列初始状态如何，在第i步排序中选出最小数据，需做n-i次比较。因此，总的比较次数为n(n-1.)2=0(n2);(2)数据的移动次数：当时始数据序列为正序时，移动次数为0.数据序列初态为反序时.，每步排序均要执行交换操作，总的移动次数取最大值3(n-1.)O干脆选择排序的平均时间困难度为O(n2);(1)稳定性分析:干脆选择排序是不稳定的。二、冒泡排序基本思想：冒泡排序是将待排序的数据看成一个个重量不等的气泡，依据轻气泡不能在重气泡之下的原则，从下往上扫描，凡遇违反本原则的状况，就进行一次交换，使轻气泡上浮。如此反复，宜到没有轻气泡在下，重气泡在上为止。12222228126666i1081288814108121010，i614101012122614141414-初第第第第第始一二三四五数步步步步步据排排排排排序序序序序后后后后后冒泡排序的程序如下：Proceduresort_bubb1.e;VarI,j,t:integer;BeginFori:=1ton-1doForj:=ndowntoi+1doIfaj-1.ajthenBegint：=aj-1.;j-1.z=aj;Aj:=t：End;程序2：programmppx;constn=7;vara:array1.nofinteger;1, j,k,t:integer;boo1.:boo1.ean;beginfori:=1tondoread(ai);i:=1;boo1.:=true;whi1.e(in)andboo1.dobeginboo1.:=fa1.se;forj:=ndowntoi+1doifaj-1.ajthenbegint:=aj-1.：aj-1.:=aj：aj:=t：boo1.:=trueend;i:=i+1.;end;fori:=1tondowrite(ai:6);writein;end.程序3：programmppx;constn=7;vara:array1.nofinteger;i,j,k,t:integer：beginfori:=1tondoread(ai);k:=n;whi1.ekdobeginj:=k-1.;k:=0;fori:=1tojdoifaiai+1.thenbegint:=ai;ai:=ai+1.：ai+1.:=t;k:=i;end;end;fori:=1tondowrite(ai:6)：writein：end.算法评价：(1) 算法的最好时间困难度：若数据的初始状态是正序的，一步扫描即可完成排序，所需的数据比较次数C和数据移动次数均达到最小值：Cmin=n-1Mmin=0;冒泡排序的最好时间困难度为O(n)。<2)算法的最坏时间困难度：若数据是反序的，须要进行n-1步排序。每步排序要进行11-i次数据的比较(1.=i=n-i),且每次比较都必需移动数据三次来达到交换数据位置。在这种状况下，比较和移动次数均达到最大值：Cmax=n(n-1)/2=0(n2)Mmax=3n(n-1)/2=0(n2)冒泡排序的最坏时间困难度为0(n2)(3)弊法的平常间困难度为0(n2)虽然冒泡排序不肯定要进行n-1步，但由于它的数据移动次数较多，故平均时间性能比干脆插入排序要差得多。(4)算法稳定性：冒泡排序是就地排序，且它是稳定的。三、插入排序将待排序的数据分成两个区域：有序区和无序区，每次将一个无序区中的数据按其大小插入到有序区中的适当位置，宜到全部无序区中的数据都插入完成为止。经过iT遍处理后,1.1.i7己排好序。第i遍处理仅将1.i插入1.1.iT的适当位置p,原来p后的元素一一向右移动一个位置,使得1.1.i乂是排好序的序列。设待排序的数据有6个，依次为12、8、10,14,6.2.其排序过程如图所示:循环变量I1281014628121014621=38101214621=48101214621=56810121421=626810I=I1281014621=21214程序如下:Proceduresort_inset;VarI,j,I:integer:BeginFori:=2tondobeginJ:=I;t:=ai：Whi1.e(aj-1.t)and(j-1.=1.)do利用whi1.e循环找插入位置BeginAj:=aj-1.;J:=j-1；End;j:=t;将数据插入到序列中End;End;算法评价：不难发觉，随数据的初始状态不同，插入排序所耗时间有很大差异。当数据的初始状态为正序，在每一步排序中仅需进行一次数据比较，且不发生数据记录的移动，即最小比较次数为n-1次。此时算法的困难度为0(n).当数据初始状态为反序时，则数据记录的比较次数和移动次都取最大值，即最大比较次数(2+3+4+n)=(nT)(n+2)2,域大移动次数为(n+4)(n-1.)2,取上述最小值和最大值的平均值，作为插入排序时所需进行关键字间的比较次数和移动记录的次数，约为n24,由此，插入排序算法的时间困难度为0(n2)。插入排序法简便，且简单实现，当待排数据量n很小时:这是一种很好的排序方法，但当n变大时，插入排序的时间开销不断增大，插入排序适用于大部分数据已形成正序或反序，只需插入个别数据的状况。四、快速排序快速排序是一种划分交换排序，它采纳了一种分治的策略，通常称其为分治法。分治法的基本思想是将原问题分为若干规模更小但结构与原问题相像的子问题，递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序的基本思想：通过一步排序将待排序的数据分割成独立的两部分，其中一部分的数据比另一部分数据小，然后分别对这两部分数据接着进行划分、排序，宜至整个序列有序。基准元素可选择：第一个或最终一个或中间一个或随机一个对于序列a1.r,快速排序分三步：(1)分解，将a1.r分解成两个非空子序列a1.q和aq+1.r,使a1.q中的数据小于aq+1.r中的数(2)递归求解。通过递归调用快速排序对左、右子区间a1.q和aq+1.r快速排序。由于分解是原地进行的，分解和递归求解后不须要做任何其他操作，a1.门的排序完。快速排序的程序如下：Proceduresort_quick(1,r:Iongint);VarI,j,x,y:Iongint;Begin1:=1;j:=r：X:=a(1.+r)div2;Whi1.ei=jdobeginWhi1.eaixdoi11c(i);Whi1.eajxdodcc(j):Ifi=jthenBeginY:=ai;i:=aj：Aj:=y;inc(i);dec(j)End;End;Ifirthensort_quick(i,r);Ifj1.thenSorjquick(1.j);End;算法评价：快速排序的时间主要耗费在划分操作上，对长度为r的区间进行划分，共需r-1次数据的比较。(1)最坏时间困难度最坏状况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数少一个。因此，快速排序必需做n-1次划分，第i次划分起先区间长度为n-i+1.,所需的比较次数为n-i(1.=i=n-1.),故总的比较次数达到最大值CmaX=n(n-1.)2=0(n2);最好时间困难度:在最好状况下，每次划分所取的基准都是当前无序区的中值记录，划分的结果是基准的左、右两个无序子区间的长充大致相等。总的关键字比较次数为O(n1.ogn).(3)平均时间困难度：尽管快速排序的最坏时间为0(n2),但就平均性而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名，它的平均时间困难度为0(n1.ogn).(4)空间困难度：快速排序在系统内部须要一个栈来实现递归，若每次划分较为匀称，需核空间为0(Iogn),最坏状况下，所需的栈空间为0(n)o五、堆排序1、堆的定义N个元素的序列k1.,k2,kn),当且仅当满意如下关系时，称之为堆。Ki=K2i或Ki=K2iKi=K2i+1.Ki=K2i+1.(i=1.,2,ndiv2)满意前一种关系称为小根堆，满意后一种关系称为大根堆。大根堆和小根堆：根结点(亦称为堆顶)的关键字是堆里全部结点关键字中最小者的堆称为小根堆。根结点(亦称为堆顶)的关键字是堆里全部结点关键字中最大者的堆称为大根堆。如下图所示：10小根椎示例大根椎示例留意：堆中任一子树亦是堆2、堆的实质在存储堆实质上是满意如下性质的完全二叉树，可用一维数组连续存储。（1） 堆对应的完全二叉树中，全部非终端结点的值均不大于（或不小于）其左右儿子结点的值。（2） 堆顶元素必为序列中n个元素的最小值（或最大值）（3） 在堆对应的完全二叉树中，若非终端结点的地址为k,则它的父亲结的地址应为k2,它的左儿子结点的地址为2k,右儿子结点的地址为2k+1.3、堆排序若在输出堆顶是最小值（或最大值）后，使得剩2余n-1个元素的序列重又建成一个堆，则得到次小值。如此反复执行，便能得到一个有序序列，这个过程称为堆排序。（1） 堆排序的特点：堆排序是树型选择排序。其特点是：在排序过程中，将R1.n看成是一棵完全二叉树的依次存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。（2） 堆排序与干脆插入排序的区分：干脆选择排序中，为了从R1.n中选出关键字最小的记录,必需进行nT次比较，然后在R2.n中选出关键字最小的记录，乂须要做n-2次比较。事实上，后面的n-2次比较中，有很多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保存这些比较结果，所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构保存部分比较结果，以削减比较次数。（3） 实现堆排序须要解决的问题：一是如何由一个无序序列建成一个初始堆；二是如何在输出堆顶元素后，调整剩余元素成为一个新的堆。解决方法：用筛选法调整堆。每趟排序起先前R1.i是以R1.为根的堆，在R与Ri交换后，新的无序区R.iT中只有R1.的值发生了改变。故除R1.可能违反堆性质外，其余任何结点为根的子树均是堆。因此，当被调整区间是R1.o.hign时，只须调整以Ruow为根的树即可。1536253070703630151025101536253070703630251510详细实现：R1.ow是左、右子树均已是堆，这两棵子树的根R21ow和R21ow+1分别是各F1.子树中数据最小的结点。若RUow不大于这两个孩子结点的数据，则RUow未违反堆性质，以R1.ow为根的树已是堆，无须调Rnow和它的两个孩子结点中数据较小者进行交换，Rsma1.1.(Rsma1.1.=min(R21ow,R21ow+1D交换。交换后双可能使结点Rsma1.1.违反堆性质。同样由于该结点的两棵子树仍旧是堆，故可重复上述的调整过程，对以Rnarge为根的树进行调整。此过程直至当前被整：否则必须将即R1.ow与调整的结点已满意堆性质，或者该结点已是叶子为止。上述过程就像过筛子一样，把较大的关键字逐层筛下去，而将较小的关键字逐层选上来。因此称为筛选法。完整的堆排序程序：Programheapsort;Constn=100:Vara:array1.100ofinteger:I,x:integer;Procedureadjust_down(I,m:integer);Varx:integer;BeginWhi1.ei*2=mdoBeginI:=i*2;If(im)and(ai+1.ai)theninc(i);IfaiaIdiv2thenBeginX:=aIdiv2;Adiv2:=ai;i:=x;EndE1.sebreak;End;End;BeginReandomize;Fori:=1tondoai:=random(100);Fori:=ndiv2downto1doadjust_down(I,n);Fori:=ndownto2doBeginX:=ai:i:=a1.;1.:=x;Adjust_down(1.,i1.);End：Fori:=1tondowrite1.n(ai);End.算法评价：堆排序的是时间主要由建立初始堆和反复重建堆这两部分的时间开销构成，堆排序的最坏时间困难度为0(n1.ogn).堆排序的平均性能较接近于最坏性能。此外，堆排序仅需一个记录大小供交换用的协助存储空间。由于建初始堆所需的比较次数较多，所以堆排序不相宜于记录数较少的文件。六、基数排序（多关键字排序）基数排序是和前面各类排序方法完全不同的一种排序方法。基数排序是借助多关键字排序的思想对单逻辑关键字进行排序的方法。什么是多关键字？每张扑克牌有两个关键字花色和而值，将扑克进行排序整理，通常是先按不同的花色分成四堆，再对每地堆按不同的面值调整依次。基数排序就是借助多关键字排序的思相，用安排和收集两种操作对单逻辑关键字进行排序的一种方法。如九个三位数分别是321,214,665,102,874,699,210,333,600因为关键字是数值，且值都在0=k=999范围内，则可把每一个十位数字看成一个关键字，即可认为k由一个关键字（k1.,k2,k3）组成，其中k1.是白位数，k2是十位数，k3是个位数。详细排序过程：第一趟排序，以个位数关键字k3作为关键字安排，个位数是0的有210.600：个位数是1的有321,安排完成后，重新收集的结果为210,600,321,102,333,214,874,665,699：其次趟拓序，以十位数关键字k2作为关键字安排，十位数是O的有600,102；十位数是】的有210,214,三趟安排收集后的结果即为最终排序结果102,210,214,321,333,600,665,699,874O基数排序程序：Progamradixsort;constn=8;type1.ink=ode;nde=ccorddata:integernext:1.ink;end;vari,j,1,m,k:integer;s:string;p,p1.:1.ink;a:array1.nofinteger;q,head:array0.9of1.ink：beginwritein(4Enterdata:,);fori:=1tondoread(ai);fori:=5downto1dobegin1.n(4Sorteddata:,);fori:=1tondowrite(ai:6);end.七、各种内部排序主法的比较排序名称干脆插入排序平均时间0(n2)0(n2)0(n2)0(n2)最坏时间0(n2)0(n2)0(n2)0(n2)0(n2)希尔排序选择排序冒泡排序快速排序0(n1.ogn)堆排序0(n1.ogn)O(n1.ogn)选择排序主法须要考虑的因素如下：(1) 若n较小(n=50),则可以采纳T脆插入乔序或选择排序。由于干脆插入排序所需的记录移动操作较选择排序多，因而当记录本身信息量较大时，用干脆选择排序较好。(2) 若文件的初始状态已经按关键字基本有序，则选用干脆插入排序或冒泡排序为宜。(3) 若11较大，则应采纳时间困难度为0(n1.ogn)的排序方法，即快速排序、堆排序。快速排序是目前基于比较的排序法中被认为是最好的方法。作业：1、军方截获的信息由n(n=1000)个数字组成，因为是敌国的高端隐私，所以一时不能破获。最原始的想法就是对这n个数进行k次提问，每次提问只是对第i个数是多少感爱好，现在要求编程完成k次提问。输入：第一行n,以下n行是截获的数字，接着一行是k,接着是k行的提问数字输出：k行依次对应提问的数字对应的输出数字样例输入：样例输出：571211211121126121734243