Pascal快速排序_图文

1、 快速排序算法的介绍分而治之方法还可以用于实现另一种完全不同的排序方法,这种排序法称为快速排序(quick sort。在这种方法中,n 个元素被分成三段(组:左段l e f t,右段r i g h t和中段m i d d l e。中段仅包含一个元素。左段中各元素都小于等于中段元素,右段中各元素都大于等于中段元素。因此l e f t和r i g h t中的元素可以独立排序,并且不必对l e f t和r i g h t的排序结果进行合并。m i d d l e中的元素被称为支点( p i v o t 。使用快速排序方法对a 0 :n-1 排序从a 0 :n-1 中选择一个元素作为m i d d l

2、 e,该元素为支点把余下的元素分割为两段left 和r i g h t,使得l e f t中的元素都小于等于支点,而right 中的元素都大于等于支点递归地使用快速排序方法对left 进行排序递归地使用快速排序方法对right 进行排序所得结果为l e f t + m i d d l e + r i g h t快速排序算法原理:(1把N个数存放在数组S中,当前集合为S中所有数。(2把当前集合第一个数定为标准数K,把S分为两个子集,左边子集S1为小于等于K的数,右边子集S2为大于等于K的数。这一操作是这样完成的:(A、设定集合第一个数作为标准数K,设定指针I、J,I指向集合第一个数,J指向集合最

3、后一个数;(B、把J向左移(J:=J-1,直到找到一个SJ<=K,则交换SI与SJ的位置,并把I后移(I:=I+1;(C、把I向右移(I:=I+1,直到找到一个SI>=K,则交换SI与SJ的位置,并把J前移(J:=J-1;(D、重复B、C直到I=J。(3依次把S1、S2作为当前集合,以第一个数作为标准数K,重复第2步,直到S1、S2及其产生的子集元素个数为1。详细过程举例如下:原序:265371611159154819 一:195151112659614837 二:115151192659614837 三:1511151926596148 37四:15111519265961483

4、7 五:151115192659614837 六:151115192637485961 七:151115192637485961 八:151115192637485961 快速排序法是所有排序方法中速度最快、效率最高的方法procedure dg(x,y:integer;X ,Y 表示集合的左右边界,即把第X 到第Y 个数进行排序var i,j,b,c,d,e,f,k:integer;begink:=nx;标准数i:=x;j:=yI ,J 为指针repeat j:=j+1;repeat 从J 往左找到一个nj<=kj:=j-1;until (nj<=k or (i>j;if

5、i<=j then begin b:=ni; ni:=nj; nj:=b; 交换i:=i+1;左指针右移end;i:=i-1;repeat 从I 往右找到一个ni>=ki:=i+1;until (ni>=k or (i>j;if i<=j then beginb:=ni;ni:=nj; nj:=b; 交换j:=j-1;end;until i>j;if j-x>0 then dg(x,j;如果集合中不止一个数则进入下一层递归,X ,J 为新边界if y-i>0 then dg(i,y; 如果集合中不止一个数则进入下一层递归,I ,Y 为新边界end

6、;var n:array1.10 of integer;a:integer;procedure dg(x,y:integer;begin clrscr;for a:=1 to 10 do read(na;dg(1,10;for a:=1 to 10 do write(na:4;end.重要提示 Ø 折半插入排序和快速排序都是执行效率比 较高的算法，经常用在数据量N>1000的时 候； Ø 在竞赛的题目中不会专门考察排序的方法， 但是这两种排序的方法是很多竞赛题目的 重要环节，所以我要求大家熟练掌握这两 种方法之一。 纪念品分组 【题目描述】元旦快到了，校学生会让乐乐负

7、责新年晚会的 纪念品发放工作。为使得参加晚会的同学所获得的纪念品价 值相对均衡，他要把购来的纪念品根据价格进行分组，但每 组最多只能包括两件纪念品，并且每组纪念品的价格之和不 能超过一个给定的整数。为了保证在尽量短的时间内发完所 有纪念品，乐乐希望分组的数目最少。 你的任务是写一个程序，找出所有分组方案中分组数最 少的一种，输出最少的分组数目。 【输入】 输入文件group.in包含n+2行: 第1行包括一个整数w，为每组纪念品价格之和的上界； 第2行为一个整数n，表示购来的纪念品的总件数；第3-n+2 行每行包含一个正整数Pi (1 Pi n，表示所对应纪 念品的价格。 【输出】 输出文件g

8、roup.out仅1行，包含一个整数，即最 少的分组数目 采取价值相对均衡的贪心策略 1、要对所有纪念品分组，则每个纪念品的价值不 可能超过上界w。 2、为了使得组数尽可能少，则采取每组纪念品价 值相对均衡的策略。 办法：不妨先将纪念品按照价值递增的顺序排序。 然后设序列的首尾指针i、j。初始时i=1，j=n。然后按 照下述贪心策略左移尾指针j、右移首指针i: 如果首尾两个物品的价格和不超过w，则这两个物 品分为一组（ii+1,jj-1）；否则尾部的物品单独成 组(jj-1。 依次类推，直至i>j为止。 按照价格递增的顺序排列纪念品a； ans:=0;最小组数初始化 i:=n;j:=1;头尾指针初始化 repeat if ai+aj<=w如