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

《信息奥训班讲义(三)排序.docx》由会员分享，可在线阅读，更多相关《信息奥训班讲义(三)排序.docx（14页珍藏版）》请在优知文库上搜索。

1、信息奥训班讲义（三）排序排序法一、选择排序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第四步排序2681

2、01412第五步排序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、换操作，总的移动次数取最大值3(n-1.)O干脆选择排序的平均时间困难度为O(n2);(1)稳定性分析:干脆选择排序是不稳定的。二、冒泡排序基本思想：冒泡排序是将待排序的数据看成一个个重量不等的气泡，依据轻气泡不能在重气泡之下的原则，从下往上扫描，凡遇违反本原则的状况，就进行一次交换，使轻气泡上浮。如此反复，宜到没有轻气泡在下，重气泡在上为止。12222228126666i1081288814108121010，i614101012122614141414-初第第第第第始一二三四五数步步步步步据排排排排排序序序序序后后后后后冒泡排序的程序如下：Proceduresort_bubb1.e;Var

4、I,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

5、-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)：wri

6、tein：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)虽然冒泡排序不肯定要

7、进行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=481

8、01214621=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

9、次。此时算法的困难度为0(n).当数据初始状态为反序时，则数据记录的比较次数和移动次都取最大值，即最大比较次数(2+3+4+n)=(nT)(n+2)2,域大移动次数为(n+4)(n-1.)2,取上述最小值和最大值的平均值，作为插入排序时所需进行关键字间的比较次数和移动记录的次数，约为n24,由此，插入排序算法的时间困难度为0(n2)。插入排序法简便，且简单实现，当待排数据量n很小时:这是一种很好的排序方法，但当n变大时，插入排序的时间开销不断增大，插入排序适用于大部分数据已形成正序或反序，只需插入个别数据的状况。四、快速排序快速排序是一种划分交换排序，它采纳了一种分治的策略，通常称其为分治法。

10、分治法的基本思想是将原问题分为若干规模更小但结构与原问题相像的子问题，递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序的基本思想：通过一步排序将待排序的数据分割成独立的两部分，其中一部分的数据比另一部分数据小，然后分别对这两部分数据接着进行划分、排序，宜至整个序列有序。基准元素可选择：第一个或最终一个或中间一个或随机一个对于序列a1.r,快速排序分三步：(1)分解，将a1.r分解成两个非空子序列a1.q和aq+1.r,使a1.q中的数据小于aq+1.r中的数(2)递归求解。通过递归调用快速排序对左、右子区间a1.q和aq+1.r快速排序。由于分解是原地进行的，分解和递归求解后

11、不须要做任何其他操作，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的区

12、间进行划分，共需r-1次数据的比较。(1)最坏时间困难度最坏状况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数少一个。因此，快速排序必需做n-1次划分，第i次划分起先区间长度为n-i+1.,所需的比较次数为n-i(1.=i=n-1.),故总的比较次数达到最大值CmaX=n(n-1.)2=0(n2);最好时间困难度:在最好状况下，每次划分所取的基准都是当前无序区的中值记录，划分的结果是基准的左、右两个无序子区间的长充大致相等。总的关键字比较次数为O(n

13、1.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)满意前一种关系称为小根堆，满意后一种关系称为大根堆。大根堆和小根堆：根结点(亦称为

14、堆顶)的关键字是堆里全部结点关键字中最小者的堆称为小根堆。根结点(亦称为堆顶)的关键字是堆里全部结点关键字中最大者的堆称为大根堆。如下图所示：10小根椎示例大根椎示例留意：堆中任一子树亦是堆2、堆的实质在存储堆实质上是满意如下性质的完全二叉树，可用一维数组连续存储。（1） 堆对应的完全二叉树中，全部非终端结点的值均不大于（或不小于）其左右儿子结点的值。（2） 堆顶元素必为序列中n个元素的最小值（或最大值）（3） 在堆对应的完全二叉树中，若非终端结点的地址为k,则它的父亲结的地址应为k2,它的左儿子结点的地址为2k,右儿子结点的地址为2k+1.3、堆排序若在输出堆顶是最小值（或最大值）后，使得剩2余n-1个元素的序列重又建成一个堆，则得到次小值。如此反复执行，便能得到一个有序序列，这个过程称为堆排序。（1） 堆排序的特点：堆排序是树型选择排序。其特点是：在排序过程中，将R1.n看成是一棵完全二叉树的依次存储结构，利用完全二叉树中双亲结点和孩子结点之间