pascal冒泡选择插入与快速排序.doc

冒泡排序 bubble sort最简单的排序方法是冒泡排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。这个算法可实现如下。procedure bubble_sort(var l:list);vari,j:position;begin1 for i:=first(l) to last(l)-1 do2 for j:=first(l) to last(l)-i do3 if ljlj+1 then 4 swap(lj,lj+1); /交换lj和lj+1end;上述算法将较大的元素看作较重的气泡，每次最大的元素沉到表尾。其中first(l)和last(l)分别表示线性表l的第一个元素和最后一个元素的位置，swap(x,y)交换变量x,y的值。上述算法简单地将线性表的位置当作整数用for循环来处理，但实际上线性表可能用链表实现；而且上述算法将线性表元素的值当作其键值进行处理。不过这些并不影响表达该算法的基本思想。今后如果不加说明，所有的算法都用这种简化方式表达。容易看出该算法总共进行了n(n-1)/2次比较。如果swap过程消耗的时间不多的话，主要时间消耗在比较上，因而时间复杂性为o(n2)。但是如果元素类型是一个很大的纪录，则swap过程要消耗大量的时间，因此有必要分析swap执行的次数。显然算法bubble_sort在最坏情况下调用n(n-1)/2次swap过程。我们假设输入序列的分布是等可能的。考虑互逆的两个输入序列l1=k1,k2,.,kn和l2=kn,kn-1,.,k1。我们知道，如果kikj，且ki在表中排在kj前面，则在冒泡法排序时必定要将kj换到ki前面，即kj向前浮的过程中一定要穿过一次ki，这个过程要调用一次swap。对于任意的两个元素ki和kj，不妨设kikj，或者在l1中ki排在kj前面，或者l2在中ki排在kj前面，两者必居其一。因此对于任意的两个元素ki和kj，在对l1和l2排序时，总共需要将这两个元素对调一次。n个元素中任取两个元素有cn2 种取法，因此对于两个互逆序列进行排序，总共要调用cn2 =n(n-1)/2次swap，平均每个序列要调用n(n-1)/4次swap。那么算法bubble_sort调用swap的平均次数为n(n-1)/4。可以对冒泡算法作一些改进，如果算法第二行的某次内循环没有进行元素交换，则说明排序工作已经完成，可以退出外循环。可以用一个布尔变量来记录内循环是否进行了记录交换，如果没有则终止外循环。冒泡法的另一个改进版本是双向扫描冒泡法（bi-directional bubble sort）。设被排序的表中各元素键值序列为：483 67 888 50 255 406 134 592 657 745 683对该序列进行3次扫描后会发现，第3此扫描中最后一次交换的一对纪录是l4和l5：50 67 255 134 | 406 483 592 657 683 745 888显然，第3次扫描(i=3)结束后l5以后的序列都已经排好序了，所以下一次扫描不必到达last(l)-i=11-4=7，即第2行的for 循环j不必到达7，只要到达4-1=3就可以了。按照这种思路，可以来回地进行扫描，即先从头扫到尾，再从尾扫到头。这样就得到双向冒泡排序算法：procedure bi-directional_bubble_sort(var l:list);varlow,up,t,i:position;begin1 low:=first(l);up:=last(l);2 while uplow do begin3 t:=low;4 for i:=low to up-1 do5 if lili+1 then begin6 swap(li,li+1);7 t:=i; end;8 up:=t;9 for i:=up downto low+1 do10 if liai then begin a0:=ai;ai:=aj;aj:=a0; end; end; 选择排序 selection sort选择排序的基本思想是：对待排序的记录序列进行n-1遍的处理，第1遍处理是将l1.n中最小者与l1交换位置，第2遍处理是将l2.n中最小者与l2交换位置，.，第i遍处理是将li.n中最小者与li交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。当然，实际操作时，也可以根据需要，通过从待排序的记录中选择最大者与其首记录交换位置，按从大到小的顺序进行排序处理。选择排序算法可实现如下。procedure selection_sort(var l:list);vari,j,s:position;begin1 for i:=first(l) to last(l)-1 do begin2s:=i;3for j:=i+1 to last(l) do4 if lj ls then s:=j; /记录li.n中最小元素的位置5swap(li,ls); /交换li,ls end; end;算法selection_sort中里面的一个for循环需要进行n-i次比较，所以整个算法需要次比较，显而易见，算法selection_sort中共调用了n-1次swap过程，即进行了n-1次交换。因而，算法selection_sort的时间复杂性f(n)=o(n2)。 参考算法：pascal语言表述的选择排序算法 procedure sort; var i,j,k:integer; begin for i:=1 to n-1 do begin k:=i; for j:=i+1 to n do if aj ak then k:=j; 找出ai.an中最小的数与ai作交换 if ki then begin a0:=ak;ak:=ai;ai:=a0; end; end; end; 思考与练习：完成并提交作业下面是一选择算法的程序段：begin1 for i:=1 to n-1 do begin2 min:=i;3 for j:= _ to n do4 if lj ls then s:=j; /选出最小元素的位置min5 if _ then swap(li,ls); /在什么条件下才交换记录? end;end;(1)在_中填上正确的语句或表达式；(2)若待排数据是3，1，2，4，5，整个算法需要进行多少次比较？多少次交换？ 插入排序 insertion sort插入排序的基本思想是，经过i-1遍处理后,l1.i-1己排好序。第i遍处理仅将li插入l1.i-1的适当位置，使得l1.i又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较li和li-1，如果li-1 li，则l1.i已排好序，第i遍处理就结束了；否则交换li与li-1的位置，继续比较li-1和li-2，直到找到某一个位置j(1ji-1)，使得lj lj+1时为止。简言之,插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。插入排序方法分直接插入排序和折半插入排序两种，这里只介绍直接插入排序，折半插入排序留到“查找”内容中进行。图1演示了对4个元素进行直接插入排序的过程，共需要(a),(b),(c)三次插入。图1 对4个元素进行插入排序在下面的插入排序算法中，为了写程序方便我们可以引入一个哨兵元素l0，它小于l1.n中任一记录。所以，我们设元素的类型elementtype中有一个常量-，它比可能出现的任何记录都小。如果常量-不好事先确定，就必须在决定li是否向前移动之前检查当前位置是否为1，若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时，就将li放入l0中，这样也可以保证在适当的时候结束第i遍处理。下面的算法中将对当前位置进行判断。插入排序算法如下：procedure selection_sort(var l:list);vari,j:position;v:elementtype;begin1 for i:=first(l)+1 to last(l) do begin2 v:=li;3 j:=i;4 while (jfirst(l)and(lj-1 v) do /循环找到插入点 begin5 lj:=lj-1; /移动元素6 j:=j-1; end;7 lj:=v; /插入元素 end;end;下面考虑算法insertion_sort的复杂性。对于确定的i，内while循环的次数为o(i)，所以整个循环体内执行了o(i)=o(i)，其中i从2到n。即比较次数为o(n2)。如果输入序列是从大到小排列的，那么内while循环次数为i-1次，所以整个循环体执行了(i-1)=n(n-1)/2次。由此可知，最坏情况下，insertion_sort要比较o(n2)次。如果元素类型是一个很大的纪录，则算法第5行要消耗大量的时间，因此有必要分析移动元素的次数。经过分析可知，平均情况下第5行要执行n(n-1)/4次，分析方法与冒泡排序的分析相同。如果移动元素要消耗大量的时间，则可以用链表来实现线性表，这样insertion_sort可以改写如下(当然前一个算法同样也适用于链表，只不过没下面这个好，但是下面的算法比较复杂)：注意：在下面的算法中链表l增加了一个哨兵单元，其中的元素为-，即线性表l的第一个元素是l.nextprocedure selection_sort_ii(var l:plist);vari,j,tmp:position;begin1 if l.next=nil then exit; /如果链表l为空则直接退出2 i:=l.next; /i指向l的第一个元素，注意，l有一个哨兵元素，因此l.next才是l的第一个元素3 while i.nextnil do begin4 tmp:=i.next; /tmp指向li的下一个位置5 j:=l;6 while (ji)and(tmp.data=j.next.data) do /从前向后找到tmp的位置，tmp应该插在j后面7 j:=j.next;8 if ji then /j=i说明不需要改变tmp的位置 begin9 i.next:=tmp.next; /将tmp从i后面摘除10 tmp.next:=j.next; /在j后面插入tmp11 j.next:=tmp; end12 else i:=i.next; /否则i指向下一个元素 end;end;上述改进算法主要是利用链表删除和插入元素方便的特性，对于数组则不适用。插入法虽然在最坏情况下复杂性为o(n2)，但是对于小规模输入来说，插入排序法是一个快速的原地置换排序法。许多复杂的排序法，在规模较小的情况下，都使用插入排序法来进行排序，比如快速排序和桶排序。这里是一个用java applet制作的插入排序演示程序。 参考算法：pascal语言表述的插入排序算法 procedure insert_sort(k,m:word); k为当前要插入的数，m为插入位置的指针 var i:word; p:0.1; begin p:=0; for i:=m downto 1 do if k=ai then exit; repeat if k am then begin am+1:=k; p:=1; end else begin am+1:=am; dec(m); end; until p=1; end;insert_sort * 主程序中为： a0:=0; for i:=1 to n do insert_sort(bi,i-1);思考与练习：完成并提交作业试对前述的插入排序、冒泡排序、选择排序进行速度比较。 快速排序 quick sort我们已经知道，在决策树计算模型下，任何一个基于比较来确定两个元素相对位置的排序算法需要(nlogn)计算时间。如果我们能设计一个需要o(n1ogn)时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。下面介绍快速排序算法，它在平均情况下需要o(nlogn)时间。这个算法是由c.a.r.hoare发明的。算法的基本思想快速排序的基本思想是基于分治策略的。对于输入的子序列lp.r，如果规模足够小则直接进行排序（比如用前述的冒泡、选择、插入排序均可），否则分三步处理： 分解(divide)：将待排序列lp.r划分为两个非空子序列lp.q和lq+1.r，使lp.q中任一元素的值不大于lq+1.r中任一元素的值。具体可通过这样的途径实现：在序列lp.r中选择数据元素lq，经比较和移动后，lq将处于lp.r中间的适当位置，使得数据元素lq的值小于lq+1.r中任一元素的值。 递归求解(conquer)：通过递归调用快速排序算法，分别对lp.q和lq+1.r进行排序。 合并(merge)：由于对分解出的两个子序列的排序是就地进行的，所以在lp.q和lq+1.r都排好序后不需要执行任何计算lp.r就已排好序，即自然合并。 这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。算法的实现算法quick_sort的实现：注意：下面的记号lp.r代表线性表l从位置p到位置r的元素的集合，但是l并不一定要用数组来实现，可以是用任何一种实现方法（比如说链表），这里lp.r只是一种记号。procedure quick_sort(p,r:position;var l:list);conste=12;varq:position;begin1 if r-p=e then insertion_sort(l,p,r)/若lp.r足够小则直接对lp.r进行插入排序 else begin2 q:=partition(p,r,l);/将lp.r分解为lp.q和lq+1.r两部分3 quick_sort(p,q,l); /递归排序lp.q4 quick_sort(q+1,r,l);/递归排序lq+1.r end;end;对线性表l1.n进行排序，只要调用quick_sort(1,n,l)就可以了。算法首先判断lp.r是否足够小，若足够小则直接对lp.r进行排序，sort可以是任何一种简单的排序法，一般用插入排序。这是因为，对于较小的表，快速排序中划分和递归的开销使得该算法的效率还不如其它的直接排序法好。至于规模多小才算足够小，并没有一定的标准，因为这跟生成的代码和执行代码的计算机有关，可以采取试验的方法确定这个规模阈值。经验表明，在大多数计算机上，取这个阈值为12较好，也就是说，当r-p=e=12即lp.r的规模不大于12时，直接采用插入排序法对lp.r进行排序。当然，比较方便的方法是取该阈值为1，当待排序的表只有一个元素时，根本不用排序(其实还剩两个元素时就已经在partition函数中排好序了)，只要把第1行的if语句改为if p=r then exit else .。这就是通常教科书上看到的快速排序的形式。注意：算法quick_sort中变量q的值一定不能等于r，否则该过程会无限递归下去，永远不能结束。因此下面在partition函数里加了限制条件，避免q=r情况的出现。算法quick_sort中调用了一个函数partition，该函数主要实现以下两个功能：1. 在lp.r中选择一个支点元素pivot; 2. 对lp.r中的元素进行整理，使得lp.q分为两部分lp.q和lq+1.r，并且lp.q中的每一个元素的值不大于pivot，lq+1.r中的每一个元素的值不小于pivot，但是lp.q和lq+1.r中的元素并不要求排好序。 快速排序法改进性能的关键就在于上述的第二个功能，因为该功能并不要求lp.q和lq+1.r中的元素排好序。函数partition可以实现如下。以下的实现方法是原地置换的，当然也有不是原地置换的方法，实现起来较为简单，这里就不介绍了。function partition(p,r:position;var l:list):position;varpivot:elementtype;i,j:position;begin1 pivot:=select_pivot(p,r,l); /在lp.r中选择一个支点元素pivot2 i:=p-1;3 j:=r+1;4 while true do begin5 repeat j:=j-1 until lj=pivot; /移动右指针，注意这里不能用while循环7 if i j then swap(li,lj) /交换li和lj8 else if jr then return j /返回j的值作为分割点9 else return j-1; /返回j前一位置作为分割点 end;end;该算法的实现很精巧。其中，有一些细节需要注意。例如，算法中的位置i和j不会超出ap.r的位置界，并且该算法的循环不会出现死循环，如果将两个repeat语句换为while则要注意当li=lj=pivot且ij时i和j的值都不再变化，会出现死循环。另外，最后一个if.then.语句很重要，因为如果pivot取的不好，使得partition结束时j正好等于r，则如前所述，算法quick_sort会无限递归下去；因此必须判断j是否等于r，若j=r则返回j的前驱。以上算法的一个执行实例如图1所示，其中pivot=lp=5：图1 partition过程的一个执行实例partition对lp.r进行划分时，以pivot作为划分的基准，然后分别从左、右两端开始，扩展两个区域lp.i和lj.r，使得lp.i中元素的值小于或等于pivot，而lj.r中元素的值大于或等于pivot。初始时i=p-1，且j=i+1，从而这两个区域是空的。在while循环体中，位置j逐渐减小，i逐渐增大，直到lipivotlj。如果这两个不等式是严格的，则li不会是左边区域的元素，而lj不会是右边区域的元素。此时若i在j之前，就应该交换li与lj的位置，扩展左右两个区域。 while循环重复至i不再j之前时结束。这时lp.r己被划分成lp.q和lq+1.r，且满足lp.q中元素的值不大于lq+1.r中元素的值。在过程partition结束时返回划分点q。寻找支点元素select_pivot有多种实现方法，不同的实现方法会导致快速排序的不同性能。根据分治法平衡子问题的思想，我们希望支点元素可以使lp.r尽量平均地分为两部分，但实际上这是很难做到的。下面我们给出几种寻找pivot的方法。1. 选择lp.r的第一个元素lp的值作为pivot； 2. 选择lp.r的最后一个元素lr的值作为pivot； 3. 选择lp.r中间位置的元素lm的值作为pivot； 4. 选择lp.r的某一个随机位置上的值lrandom(r-p)+p的值作为pivot； 按照第4种方法随机选择pivot的快速排序法又称为随机化版本的快速排序法，在下面的复杂性分析中我们将看到该方法具有平均情况下最好的性能，在实际应用中该方法的性能也是最好的。下面是一个快速排序的java applet演示程序，该程序使用第一种pivot选择法，即选lp为pivot，因此partition过程作了一些简化，与我们这里的partition过程实现方法不同，但功能相同。该程序是针对用数组实现的线性表，用c语言实现的。参考算法：pascal语言表述的快速排序算法 procedure sort(l,r:integer); var i,j,mid:integer; begin i:=l;j:=r; mid:=a(l+r) div 2; 将当前序列在中间位置的数定义为中间数 repeat while ai mid do inc(i); 在左半部分寻找比中间数大的数 while mid aj do dec(j); 在右半部分寻找比中间数小的数 if ij; if l j then sort(l,j); 若未到两个数的边界，则递归搜索左右区间 if i r then sort(i,r); end;sort 思考与练习：完成并提交作业1、仔细阅读下面的pascal程序，并回答有关问题。procedure px(var a:array1.500 of integer,n:integer);var i,j,x:integer;b:boolean;begin b:=true;i:=1; while (i n) and b do beginb:=false;for j:=1 to _ do if _ thenbeginx:=aj;aj:=aj+1;aj+1:=x;_ end; i:=i+1; end;end;(1)在_中填上正确的语句或表达式；(2)该过程使用的是什么排序方式?(3)当数组a的元素初始时已为递增排列时，该过程运行时会进行几次比较？几次交换？(4)若a是递减排列，比较和交换次数又是多少？ 2、给出n个学生的考试成绩表，每个数据记录由学生的姓名和成绩组成，试设计一个算法：(1)按成绩高低次序,输出每个学生在考试中获得的名次,成绩相同的名次相同