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

排 序 法一、 选择排序selection sort基本思想：每一步从待排序的数据中选择最小（此处以正序为例，若为反序则正好相反）的数据，顺序放在已排好序的子序列的最后，直到全部数据排序完毕。对待排序的记录序列进行n-1遍的处理，第1遍处理是将L1.n中最小者与L1交换位置，第2遍处理是将L2.n中最小者与L2交换位置，.，第i遍处理是将Li.n中最小者与Li交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。初始状态 12 8 10 14 6 2 第一步排序 2 8 10 14 6 12 第二步排序 2 6 10 14 8 12 第三步排序 2 6 8 14 10 12 第四步排序 2 6 8 10 14 12 第五步排序 2 6 8 10 12 14直接选择排序的程序如下：Procedure sort_select;Var I,j,k,t:integer;Begin For i:=1 to n-1 do BeginK:=I;For j:=i+1 to n do If akaj then k:=j;If kI then Begin t:=ai; Ai:=ak; Ak:=t; End; End;End;算法评价：（1） 数据比较次数无论数据序列初始状态如何，在第i步排序中选出最小数据，需做n-i次比较。因此，总的比较次数为n(n-1)/2=O(n2);（2）数据的移动次数：当初始数据序列为正序时，移动次数为0.数据序列初态为反序时，每步排序均要执行交换操作，总的移动次数取最大值3(n-1)。直接选择排序的平均时间复杂度为O(n2);（1） 稳定性分析：直接选择排序是不稳定的。二、 冒泡排序基本思想：冒泡排序是将待排序的数据看成一个个重量不等的气泡，依据轻气泡不能在重气泡之下的原则，从下往上扫描，凡遇违反本原则的情况，就进行一次交换，使轻气泡“上浮”。如此反复，直到没有轻气泡在下，重气泡在上为止。 12 2 2 2 2 2 8 12 6 6 6 6 10 8 12 8 8 8 14 10 8 12 10 10 6 14 10 10 12 12 2 6 14 14 14 14 初 第 第 第 第 第 始 一 二 三 四 五 数 步 步 步 步 步 据 排 排 排 排 排 序 序 序 序 序 后 后 后 后 后冒泡排序的程序如下：Procedure sort_bubble;Var I,j,t:integer;Begin For i:=1 to n-1 do For j:=n downto i+1 do If aj-1aj then Begin t:=aj-1; Aj-1:=aj; Aj:=t; End;程序2：program mppx;const n=7;var a:array1.n of integer; i,j,k,t:integer; bool:boolean;begin for i:= 1 to n do read(ai); i:=1;bool:=true; while (iaj then begin t:=aj-1;aj-1:=aj;aj:=t;bool:=true end; i:=i+1; end; for i:= 1 to n do write(ai:6); writeln;end.程序3：program mppx;const n=7;var a:array1.n of integer; i,j,k,t:integer;beginfor i:= 1 to n do read(ai); k:=n; while k0 do begin j:=k-1;k:=0; for i:=1 to j do if aiai+1 then begin t:=ai;ai:=ai+1;ai+1:=t;k:=i;end; end;for i:= 1 to n do write(ai:6);writeln;end.算法评价：（1） 算法的最好时间复杂度：若数据的初始状态是正序的，一步扫描即可完成排序，所需的数据比较次数C和数据移动次数均达到最小值：Cmin=n-1 Mmin=0;冒泡排序的最好时间复杂度为O(n)。（2） 算法的最坏时间复杂度：若数据是反序的，需要进行n-1步排序。每步排序要进行n-i次数据的比较（1=it) and (j-1=1) do 利用while循环找插入位置 Begin Aj:=aj-1; J:=j-1; End; Aj:=t; 将数据插入到序列中 End;End;算法评价：不难发现，随数据的初始状态不同，插入排序所耗时间有很大差异。当数据的初始状态为正序，在每一步排序中仅需进行一次数据比较，且不发生数据记录的移动，即最小比较次数为n-1次。此时算法的复杂度为O（n）。当数据初始状态为反序时，则数据记录的比较次数和移动次都取最大值，即最大比较次数（2+3+4+n）=(n-1)(n+2)/2,最大移动次数为(n+4)(n-1)/2，取上述最小值和最大值的平均值，作为插入排序时所需进行关键字间的比较次数和移动记录的次数，约为n2/4，由此，插入排序算法的时间复杂度为O(n2)。插入排序法简便，且容易实现，当待排数据量n很小时，这是一种很好的排序方法，但当n变大时，插入排序的时间开销不断增大，插入排序适用于大部分数据已形成正序或反序，只需插入个别数据的情况。四、 快速排序快速排序是一种划分交换排序，它采用了一种分治的策略，通常称其为分治法。分治法的基本思想是将原问题分为若干规模更小但结构与原问题相似的子问题，递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序的基本思想：通过一步排序将待排序的数据分割成独立的两部分，其中一部分的数据比另一部分数据小，然后分别对这两部分数据继续进行划分、排序，直至整个序列有序。基准元素可选择：第一个或最后一个或中间一个或随机一个对于序列a1.r，快速排序分三步：（1） 分解，将a1.r分解成两个非空子序列a1.q和aq+1.r,使a1.q中的数据小于aq+1.r中的数（2） 递归求解。通过递归调用快速排序对左、右子区间a1.q和aq+1.r快速排序。（3） 合并。由于分解是原地进行的，分解和递归求解后不需要做任何其他操作，a1.r的排序完。快速排序的程序如下：Procedure sort_quick(l,r:longint);Var I,j,x,y:longint;Begin I:=l;j:=r; X:=a(l+r)div 2; While i=j do begin While aix do dec(j); If i=j then Begin Y:=ai; Ai:=aj; Aj:=y; inc(i); dec(j) End; End; If il then sort_quick(l,j);End; 算法评价：快速排序的时间主要耗费在划分操作上，对长度为r的区间进行划分，共需r-1次数据的比较。（1） 最坏时间复杂度最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准左边的子区间为空（或右边的子区间为空），而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数少一个。因此，快速排序必须做n-1次划分，第i次划分开始区间长度为n-i+1,所需的比较次数为n-i(1=i=n-1),故总的比较次数达到最大值Cmax=n(n-1)/2=O(n2);(2)最好时间复杂度：在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长充大致相等。总的关键字比较次数为O(nlogn).(3)平均时间复杂度：尽管快速排序的最坏时间为O(n2)，但就平均性而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名，它的平均时间复杂度为O(nlogn)。(4)空间复杂度：快速排序在系统内部需要一个栈来实现递归，若每次划分较为均匀，需栈空间为O（logn），最坏情况下，所需的栈空间为O(n)。五、 堆排序1、 堆的定义N个元素的序列k1,k2,kn，当且仅当满足如下关系时，称之为堆。 Ki=K2i Ki=K2i+1 (i=1,2,n div 2)满足前一种关系称为小根堆，满足后一种关系称为大根堆。大根堆和小根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者的堆称为大根堆。如下图所示：7010 30363615101525703025152530367010703025361510 小根椎示例 大根椎示例注意：堆中任一子树亦是堆2、 堆的实质在存储堆实质上是满足如下性质的完全二叉树，可用一维数组连续存储。（1） 堆对应的完全二叉树中，所有非终端结点的值均不大于（或不小于）其左右儿子结点的值。（2） 堆顶元素必为序列中n个元素的最小值（或最大值）（3） 在堆对应的完全二叉树中，若非终端结点的地址为k，则它的父亲结的地址应为k/2，它的左儿子结点的地址为2k，右儿子结点的地址为2k+1.3、 堆排序若在输出堆顶是最小值（或最大值）后，使得剩2余n-1个元素的序列重又建成一个堆，则得到次小值。如此反复执行，便能得到一个有序序列，这个过程称为堆排序。（1） 堆排序的特点： 堆排序是树型选择排序。其特点是：在排序过程中，将R1.n看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。（2） 堆排序与直接插入排序的区别：直接选择排序中，为了从R1.n中选出关键字最小的记录，必须进行n-1次比较，然后在R2.n中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保存这些比较结果，所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构保存部分比较结果，以减少比较次数。（3） 实现堆排序需要解决的问题：一是如何由一个无序序列建成一个初始堆；二是如何在输出堆顶元素后，调整剩余元素成为一个新的堆。解决办法：用“筛选法”调整堆。每趟排序开始前R1.i是以R1为根的堆，在R1与Ri交换后，新的无序区R1.i-1中只有R1的值发生了变化。故除R1可能违反堆性质外，其余任何结点为根的子树均是堆。因此，当被调整区间是Rlow.hign时，只须调整以Rlow为根的树即可。具体实现：Rlow是左、右子树均已是堆，这两棵子树的根R2low和R2low+1分别是各自子树中数据最小的结点。若Rlow不大于这两个孩子结点的数据，则Rlow未违反堆性质，以Rlow为根的树已是堆，无须调整；否则必须将Rlow和它的两个孩子结点中数据较小者进行交换，即Rlow与Rsmall(Rsmall=min(R2low,R2low+1)交换。交换后双可能使结点Rsmall违反堆性质。同样由于该结点的两棵子树仍然是堆，故可重复上述的调整过程，对以Rlarge为根的树进行调整。此过程直至当前被调整的结点已满足堆性质，或者该结点已是叶子为止。上述过程就像过筛子一样，把较大的关键字逐层筛下去，而将较小的关键字逐层选上来。因此称为“筛选法”。完整的堆排序程序：Program heapsort;Const n=100;Var a:array1.100 of integer; I,x:integer;Procedure adjust_down(I,m:integer);Var x:integer;Begin While i*2=m do BeginI:=i*2;If (iai) then inc(i);If aiaI div 2 then Begin X:=aI div 2; AI div 2:=ai; Ai:=x; EndElse break; End;End;Begin Reandomize; For i:=1 to n do ai:=random(100); For i:=n div 2 downto 1 do adjust_down(I,n); For i:=n downto 2 do BeginX:=ai;Ai:=a1;A1:=x;Adjust_down(1,i-1); End; For i:=1 to n do writeln(ai);End.算法评价：堆排序的是时间主要由建立初始堆和反复重建堆这两部分的时间开销构成，堆排序的最坏时间复杂度为O(nlogn).堆排序的平均性能较接近于最坏性能。此外，堆排序仅需一个记录大小供交换用的辅助存储空间。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。六、 基数排序（多关键字排序）基数排序是和前面各类排序方法完全不同的一种排序方法。基数排序是借助多关键字排序的思想对单逻辑关键字进行排序的方法。什么是多关键字？每张扑克牌有两个“关键字”花色和面值，将扑克进行排序整理，通常是先按不同的花色分成四堆，再对每地堆按不同的面值调整顺序。基数排序就是借助多关键字排序的思相，用“分配”和“收集”两种操作对单逻辑关键字进行排序的一种方法。如九个三位数分别是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作为关键字分配，十位数是0的有600，102；十位数是1 的有210，214，三趟分配收集后的结果即为最终排序结果102，210，214，321，333，600，665，699，874。基数排序程序：Progam radixsort;const n=8;type link=node; node=record data:integer; next:link; end;var i,j,l,m,k:integer; s:string; p,p1:link; a:array1.n of integer; q,head:array0.9 of link;beginwriteln(Enter data:);for i:=1 to n do read(ai);for i:=5 downto 1 do begin for j:=0 to 9 do begin new(headj);headj.next:=nil;qj:=headj end; for j:=1 to n do begin str(aj,s); for k:=1 to 5-length(s) do s:=0+ s; m:=ord(si)-48; new(p); p.data:=aj; p.next:=nil; qm.next:=p; qm:=p; end; l:=0