《排序算法及应用》PPT课件.pptVIP

第六讲 排序算法及应用,排序算法的种类：,1、选择排序 2、冒泡排序 3、插入排序 4、快速排序 5、堆排序,1、选择排序 算法基本思想： 对待排序的序列进行n-1遍处理： 第1遍处理是从a1,a2,an中选择最小的放在a1位置； 第2遍处理是从a2,a3,an中选择最小的放在a2位置； 第I遍处理是将a i ,a i+1,an中最小的数与a i 交换位置，这样经过第i遍处理后，ai是所有的中的第i小。即前i个数就已经排好序了。 N-1遍处理后，剩下的最后一个一定是最大的，不需要再处理了。,a:待排序的数组；/从小到大排序 简单选择排序： for i:=1 to n-1 do 从第一个元素开始,进行n-1遍处理 for j:=i+1 to n do 第i遍处理 If aiaj then 交换ai和aj begin t:=ai; ai:=aj; aj:=t; end;,算法的改进: 减少交换次数,for i:=1 to n-1 do begin k:=i; for j:=i+1 to n do if aji then begin t:=ak; ak:=ai; ai:=t; end; end;,排序的关键字： 20 30 10 15 16 13 8,2、冒泡排序算法： 基本思想：（从小到大排序） 将待排序的数据看作竖派排的一列”气泡“，小的数据比较轻，从而要上浮。 共进行n-1遍处理，每一遍处理，就是从底向上检查序列，如果相邻的两个数据顺序不对，即轻（小）的在下面，就交换他们的位置。 第一遍处理完后，“最轻”的就浮到上面。 第二遍处理完后，“次轻”的就浮到上面。 共需要n-1遍处理即完成排序。,/ 简单的冒泡排序 for i:=1 to n-1 do for j:=n downto i+1 do if ajaj-1 then begin t:=aj; aj:=aj-1; aj-1:=t; end;,/ 判断标志： flag=true 已有序 /改进后的冒泡排序 for i:=1 to n-1 do begin flag:=true; for j:=n downto i+1 do if ajaj-1 then begin t:=aj; aj:=aj-1; aj-1:=t; flag:=false; end; if flag=true then break; /某一轮没有交换，说明都已经有序了 end;,算法的改进,关键字 20 30 40 50 60 10,测定时间的方法： 通过访问MemLSeg0040:$006C来获取当前时间，它返回的是当日零时到现在所经过的时间，单位约为55毫秒（约1/18.2秒）。,测定执行的时间 Starttime,endtime:longint; Starttime:= MemLSeg0040:$006C; endtime:= MemLSeg0040:$006C; Writeln(endtime-starttime)/18.2:0:2); 语句组2运行的时间 或： Writeln(MemLSeg0040:$006C -starttime)/18.2:0:2);,StartTime := MemLSeg0040:$006C; for i:=1 to n-1 do for j:=n downto i+1 do if ajaj-1 then begin t:=aj; aj:=aj-1; aj-1:=t; end; writeln(MemLSeg0040:$006c - StartTime)/18.2:0:2);,3、插入排序算法:,基本思想： 经过i-1遍处理后，a1,a2,ai-1已排好序。 第i遍处理是将元素ai插入到a1,a2,ai-1的适当的位置，从而使得a1,a2,ai-1,ai又是排好的序列。,a:array0n of integer; a0记录当前待插元ai for i:=2 to n do begin a0:=ai; 取第i个元素作为待插入元素 j:=i-1; 从已排好的最后一个ai-1开始比较 while a0=aj时循环结束 aj+1:=a0; 在第j+1个位置插入ai元素 end;,4、快速排序算法：,基本思想：把待排序的n个元素放到一个中的任一个元素数组中，先取数组中的某一个元素作为一个基准元素，把这个元素放到数组中合适的位置，同时对其他元素进行调整，使得在这个基准元素的右边的所有元素都比这个基准元素大，而基准元素左边的元素都比它小。也就是说，这个基准元素当前所在的位置就是排序后的最终位置。然后再对基准元素的前后两个区间分别进行快速排序，直到每个区间为空后者只有一个元素时，整个快速排序结束。,方法一： 取数组中的第一个元素作为基准元素： 把待排序的数组按照基准元素分为左右两部分的过程称为快速排序的一次划分（一趟排序）。 待排数组：a1 an。 一次划分的过程： 设I，j两个指针，开始时，i 1，j n，x ai：基准元素。如果aj=x 那么j j-1，直到找到ajx，然后：aj ai。,procedure qsort(s,t:integer);s:待排序数组首元素下标,t:末尾元素下标 var i,j:integer; x:integer; begin i:=s; j:=t; x:=as; x:首元素为基准元素 while i=x) and(ji) do dec(j); 从未部找比x小的元素aj if ji then begin ai:=aj; inc(i); end; 把aj放在i处,j处空着 while (ai=x)and(ij) do inc(i); 继续从前边找比x大元素ai if ij then begin aj:=ai; dec(j); end; 把ai移动到j位置处,i处空着 end; ai:=x; 基准元素x放到合适的i位置 if s(i-1) then qsort(s,i-1); 对基准元素x的左区间再进行快速排序 if (i+1)t then qsort(i+1,t); 对基准元素x的右区间再进行快速排序 end;,主程序的调用: qsort(1,n);,方法二:取中间元素为基准元素的算法:,procedure qsort(l,r:integer); var i,j,mid:integer; temp:integer; begin i:=l;j:=r; mid:=a(l+r) div 2; 将当前序列在中间位置的数定义为中间数 repeat while aimid do dec(j);在右半部分寻找比中间数小的数 if ij; if lj then qsort(l,j); 若未到两个数的边界，则递归搜索左右区间 if ir then qsort(i,r); end;sort,排序算法的应用,1、排队接水 有n个人排队在一个水笼头前接水，每个人的接水时间互不相等。找出一种n个人排队接水的顺序，使他们平均等待的时间最短。 输入： 第一行：n(100). 第二行：依次为n个人的接水时间。 输出： 第一行：所有人的平均等待时间。 第二行：接水的顺序。 样例： 输入：5 2 6 1 3 8 输出： 8.40 3 1 4 2 5,var num,t:array1100 of integer; n,i,j,sum,tem:integer; begin readln(n); for i:=1 to n do read(ti); for i:=1 to n do numi:=i; for i:=1 to n-1 do for j:=i+1 to n do if titj then begin tem:=ti; ti:=tj; tj:=tem; tem:=numi; numi:=numj; numj:=tem; end; sum:=0; for i:=1 to n do sum:=sum+(n+1-i)*ti; writeln(sum/n:0:2); for i:=1 to n-1 do write(numi, ); writeln(numn); end.,2、主油管的最优位置 Olay教授正在为一家石油公司咨询。该公司正在设计建造一条由东向西的管道，该管道要穿过一个有n口井的油田。从每口井中都有一条喷油管沿最短路径与主管道直接相连（或南或北）。 给定各个井的X和Y坐标，Olay教授如何才能选择主管道的最优位置（即使得个喷管长度总和最小的位置）。 输入：3 2 3 3 7 5 4 输出：4,3、成绩排名 【问题描述：】 根据期末考试的成绩单信息，把所有的学生按总分从高到低的顺序输出。 【输入：】 第一行：学生的个数n（n=100）。 以下n行：每行包含一个学生的信息，依次是：学号（1n）、姓名、语文成绩、数学成绩。他们中间有且仅有一个空格隔开，输入信息中没有多余的空格。姓名全是字母，长度不大于200，各科成绩不超过100。 【输出：】 N行，每行包含一个学生的信息：学号、姓名、总分。中间用一个空格隔开，不能有多余的空格。总分相同的学生，学号大的在前。 【样例输入：】 4 3 abc 40 50 2 gd 50 40 1 wr 60 60 4 dsd 10 20,【样例输出：】 1 wr 120 3 abc 90 2 gd 90 4 dsd 30,4、区间合并 【问题描述：】 从键盘上任意输入n个区间，然后按从小到大的顺序依次输出n个区间的并集。 【输入：】 第一行，区间个数n（=1000） 以下n行，每行两个整数a、b（-1000000000ab1000000000）,相应区间的坐标，中间 一个空格。 【输出：】 n个区间的并集，n行，每行一个区间，坐标轴的左边的区间先输出。 【样例输入：】 3 1 4 3 5 7 8 【样例输出：】 1 5 7 8,区间的合并,注意： 1、区间个数n的范围（=1000） 2、区间的数据类型和范围： 整数类型、-109-109,算法一：离散化,思路： 设fi:01,初始值全部为0。 每读入一个区间 a b For i:=1 to n For j:=a to b do fj=1 最后输出 fj=1 的区间。 时间复杂度： 1012，只能过部分数据。,算法二：直接合并,1、按每个区间的左端的的值升序排列。 由于N=1000,任意排序算法。 注意数据结构的设置: 记录类型 二维数组： a:array11000,12 of longint; a:array11000of array12 of longint,2、合并过程, 输出第一个区间 的左端点坐标（最小的） 依次处理后面的 n-1 的区间。,If aI,2=tail Tail不变,If (aI,1=tail)and(tail=aI,2) Tail=aI,2,If tailaI,1 Writeln(tail); Write(aI,1); Tail:=aI,2;,5、修理牛棚 在一个暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚没有住满。有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度,并且一个紧挨着另一个被排成一行。 自门遗失以后,农民约翰很快在牛棚门口之前竖立起新的木板。 他的新木材供应者将会供应他任何他想要的长度,但是供应者只能提供有限数目的木板。 农民约翰想将他购买的木板总长度减到最少。 给出可能买到的木板最大的数目M(1= M=50)；牛棚的总数S(1= S=200)；牛棚里牛的数目C(1 = C =S)。牛所在的牛棚的编号number(1 = number = S),