第6讲 排序算法及应用

1、第六讲排序算法及应用 刘建国刘建国 昌邑市卜庄初中昌邑市卜庄初中 排序算法的种类：排序算法的种类： 1、选择排序、选择排序 2、冒泡排序、冒泡排序 3、插入排序、插入排序 4、快速排序、快速排序 5、堆排序、堆排序 1、选择排序、选择排序 算法基本思想：算法基本思想： 对待排序的序列进行对待排序的序列进行n-1遍处理：遍处理： 第第1 1遍处理是从遍处理是从a1,a2,ana1,a2,an 中选择最小的放在中选择最小的放在a1a1位置；位置； 第第2 2遍处理是从遍处理是从a2,a3,ana2,a3,an 中选择最小的放在中选择最小的放在a2a2位置；位置； 第第I I遍处理是将遍处理是将a

2、i ,a i+1,ana i ,a i+1,an中最小的数与中最小的数与a i a i 交换位置，这交换位置，这 样经过第样经过第i i遍处理后，遍处理后，aiai 是所有的中的第是所有的中的第i i小。即前小。即前i i个数就已经排个数就已经排 好序了。好序了。 N-1N-1遍处理后，剩下的最后一个一定是最大的，不需要再处理了。遍处理后，剩下的最后一个一定是最大的，不需要再处理了。 a:待排序的数组；待排序的数组；/从小到大排序从小到大排序 简单选择排序：简单选择排序： for i:=1 to n-1 do 从第一个元素开始从第一个元素开始,进行进行n-1遍处理遍处理 for j:=i+1

3、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 ajak then k:=j; if ki then begin t:=ak; ak:=ai; ai:=t; end; end; 排序的关键字：排序的关键字： 20 30 10 15 16 13 8 2、冒泡排序算法：、冒泡排序算法： 基本思想基本思想：（从小到大排序）：（从小到大排序） 将待

4、排序的数据看作竖派排的一列将待排序的数据看作竖派排的一列”气泡气泡“，小的数据，小的数据 比较轻，从而要上浮。比较轻，从而要上浮。 共进行共进行n-1遍处理，每一遍处理，就是从底向上检查序列，遍处理，每一遍处理，就是从底向上检查序列， 如果相邻的两个数据顺序不对，即轻（小）的在下面，就交如果相邻的两个数据顺序不对，即轻（小）的在下面，就交 换他们的位置。换他们的位置。 第一遍处理完后，第一遍处理完后，“最轻最轻”的就浮到上面。的就浮到上面。 第二遍处理完后，第二遍处理完后，“次轻次轻”的就浮到上面。的就浮到上面。 共需要共需要n-1遍处理即完成排序。遍处理即完成排序。 / 简单的冒泡排序简单的

5、冒泡排序 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; /某一

6、轮没有交换，说明都已经有序了某一轮没有交换，说明都已经有序了 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); 语

7、句组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-1i-1遍处理后，遍处理后，a1,a2,a1,a2,ai-

8、1,ai-1已排好序。已排好序。 第第i i遍处理是将元素遍处理是将元素aiai 插入到插入到a1,a2,a1,a2,ai-1,ai-1的适当的位置，从的适当的位置，从 而使得而使得a1,a2,a1,a2,ai-1,ai,ai-1,ai又是排好的序列。又是排好的序列。 a:array0.n of integer; a:array0.n of integer; a0a0记录当前待插元记录当前待插元aiai for i:=2 to n dofor i:=2 to n do begin begin a0:=ai a0:=ai; ; 取第取第i i个元素作为待插入元素个元素作为待插入元素 j:=i-1

9、; j:=i-1; 从已排好的最后一个从已排好的最后一个ai-1ai-1开始比较开始比较 while a0aj while a0=aja0=aj 时循环结束时循环结束 aj+1:=a0; aj+1:=a0; 在第在第j+1j+1个位置插入个位置插入aiai 元素元素 end; end; 4、快速排序算法：、快速排序算法： 基本思想：把待排序的n个元素放到一个中的任一个元素数组中，先取数组取数组 中的某一个元素作为一个基准元素中的某一个元素作为一个基准元素，把这个元素放到数组中合适的位置，同时对 其他元素进行调整，使得在这个基准元素的右边的所有元素都比这个基准元素大， 而基准元素左边的元素都比它

10、小。也就是说，这个基准元素当前所在的位置就是 排序后的最终位置。然后再对基准元素的前后两个区间分别进行快速排序，直到 每个区间为空后者只有一个元素时，整个快速排序结束。 方法一：方法一： 取数组中的第一个第一个元素作为基准元素： 把待排序的数组按照基准元素分为左右两部分的过程称为快速排序的一次 划分（一趟排序）。 待排数组：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:末

11、尾元素下标末尾元素下标 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位置

12、处位置处,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:in

13、teger; 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个人排队接水的顺序，使他们平均等个人

14、排队接水的顺序，使他们平均等 待的时间最短。待的时间最短。 输入：输入： 第一行：第一行：n(tj 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教授正在为一家石油公司咨询。该公司正在设计建造 一条由东向西的

15、管道，该管道要穿过一个有n口井的油田。 从每口井中都有一条喷油管沿最短路径与主管道直接相连 （或南或北）。 给定各个井的X和Y坐标，Olay教授如何才能选择主管道 的最优位置（即使得个喷管长度总和最小的位置）。 输入：3 2 3 3 7 5 4 输出：4 var x,y:array1.100of integer; n,i,j,k,m:integer; begin read(n); 油井个数 for i:=1 to n do read(xi,yi); 每个油井的坐标 for i:=1 to n-1 do 冒泡排序纵坐标：从小到大 for j:=n downto i+1 do if yjyj-1

16、then begin k:=yj; yj:=yj-1; yj-1:=k; end; if n mod 2=1 then write(ytrunc(n+1)/2) 输出中间值 else write(ytrunc(n/2), ,ytrunc(n/2+1); 输出中间区间 end. 3、成绩排名、成绩排名 【问题描述：【问题描述：】 根据期末考试的成绩单信息，把所有的学生按总分从高到低的顺序输出。根据期末考试的成绩单信息，把所有的学生按总分从高到低的顺序输出。 【输入：【输入：】 第一行：学生的个数第一行：学生的个数n（n=100）。）。 以下以下n行：每行包含一个学生的信息，依次是：学号（行：每行

17、包含一个学生的信息，依次是：学号（1.n）、姓名、语文）、姓名、语文 成绩、数学成绩。他们中间有且仅有一个空格隔开，输入信息中没有多余的成绩、数学成绩。他们中间有且仅有一个空格隔开，输入信息中没有多余的 空格。姓名全是字母，长度不大于空格。姓名全是字母，长度不大于200，各科成绩不超过，各科成绩不超过100。 【输出：【输出：】 N行，每行包含一个学生的信息：学号、姓名、总分。中间用一个空格隔开，行，每行包含一个学生的信息：学号、姓名、总分。中间用一个空格隔开， 不能有多余的空格。总分相同的学生，学号大的在前。不能有多余的空格。总分相同的学生，学号大的在前。 【样例输入：【样例输入：】 4 3

18、 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）,相相 应区间的坐标，中

19、间应区间的坐标，中间 一个空格。一个空格。 【输出：【输出：】 n个区间的并集，个区间的并集，n行，每行一个区间，坐标轴的左边的区间先输出。行，每行一个区间，坐标轴的左边的区间先输出。 【样例输入：【样例输入：】 3 5 4 8 【样例输出：【样例输出：】 1 5 7 8 区间的合并区间的合并 注意：注意： 1 1、区间个数、区间个数n n的范围（的范围（=1000=1000） 2 2、区间的数据类型和范围：、区间的数据类型和范围： 整数类型、整数类型、-10-109 9-10-109 9 算法一：离散化算法一：离散化 思路：思路： 设设fi:0.1,fi:0.1,初始值全部为初始值全部为0

20、0。 每读入一个区间每读入一个区间a ba b For i:=1 to n For i:=1 to n For j:=a to b do fj For j:=a to b do fj=1=1 最后输出最后输出 fjfj=1 =1 的区间。的区间。 时间复杂度：时间复杂度： 101012 12，只能过部分数据。 ，只能过部分数据。 算法二：直接合并算法二：直接合并 1 1、按每个区间的、按每个区间的左左端的的值升序排列。端的的值升序排列。 由于由于N=1000,N=1000,任意排序算法。任意排序算法。 注意数据结构的设置注意数据结构的设置: : 记录类型记录类型 二维数组：二维数组： a:ar

21、ray1.1000,1.2 of longinta:array1.1000,1.2 of longint; ; a:array1.1000of array1.2 of longint a:array1.1000of array1.2 of longint 2 2、合并过程、合并过程 输出第一个区间的左端点坐标（最小的）输出第一个区间的左端点坐标（最小的） 依次处理后面的依次处理后面的 n-1 n-1 的区间。的区间。 If aI,2=tailIf aI,2=tail TailTail不变不变 If If (aI,1=tail)and(tail(aI,1=tail)and(tail=aI,2)=

22、aI,2) Tail=aI,2Tail=aI,2 If tailaI,1If tailaI,1 Writeln(tailWriteln(tail);); Write(aI,1);Write(aI,1); Tail:=aI,2;Tail:=aI,2; write(a1,1, ); write(a1,1, ); tail:=a1,2; tail:=a1,2; for i:=2 to n do for i:=2 to n do begin begin if (ai,1=tail)and(tail if (ai,1=tail)and(tail=ai,2) /2=ai,2) /2 then tail:=

23、ai,2; then tail:=ai,2; if tailai,1 then /3 if tailai,1 then /3 begin begin writeln(tail writeln(tail);); write(ai,1, ); write(ai,1, ); tail:=ai,2; tail:=ai,2; end; end; end; end; writeln(tail writeln(tail);); 5、修理牛棚、修理牛棚 在一个暴风雨的夜晚在一个暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。农民约翰的牛棚的屋顶、门被吹飞了。 好在许多好在许多 牛正在度假，所以牛棚没有住满。有

24、些牛棚里有牛，有些没有。牛正在度假，所以牛棚没有住满。有些牛棚里有牛，有些没有。 所有的牛棚所有的牛棚 有相同的宽度有相同的宽度,并且一个紧挨着另一个被排成一行。并且一个紧挨着另一个被排成一行。 自门遗失以后自门遗失以后,农民约翰农民约翰 很快在牛棚门口之前竖立起新的木板。很快在牛棚门口之前竖立起新的木板。 他的新木材供应者将会供应他任何他他的新木材供应者将会供应他任何他 想要的长度想要的长度,但是供应者只能提供有限数目的木板。但是供应者只能提供有限数目的木板。 农民约翰想将他购买的木农民约翰想将他购买的木 板总长度减到最少。板总长度减到最少。 给出可能买到的木板最大的数目给出可能买到的木板最

25、大的数目M(1= M=50)；牛棚；牛棚 的总数的总数S(1= S=200)；牛棚里牛的数目；牛棚里牛的数目C(1 = C =S)。牛所在的牛棚的编。牛所在的牛棚的编 号号number(1 = number = S),计算拦住所有有牛的牛棚所需木板的最小总计算拦住所有有牛的牛棚所需木板的最小总 长度。长度。 输出所需木板的最小总长度（每个牛棚的宽度为输出所需木板的最小总长度（每个牛棚的宽度为1）作为的答案。）作为的答案。 输入：输入： 第第1行：行：M S C（中间用空格分开）（中间用空格分开） 第第 2行到行到c+1共共c行，每行一个个整数，表示牛所占的牛棚的编号。行，每行一个个整数，表示牛

26、所占的牛棚的编号。 输出：单独的一行包含一个整数，表示所需木板的最小总长度。输出：单独的一行包含一个整数，表示所需木板的最小总长度。 样例：样例： 输入：输入： 4 50 183 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43 输出：输出： 25 提示：提示： 一种最优的安排是用板拦住牛棚一种最优的安排是用板拦住牛棚3-8,14-21,25-31,40-43. 6、潜水比赛、潜水比赛 在马其顿王国举行了一次潜水比赛。其中一个项目是从高山上跳下在马其顿王国举行了一次潜水比赛。其中一个项目是从高山上跳下 水，再潜水达到终点。这是一个团体项目，一支队伍

27、由水，再潜水达到终点。这是一个团体项目，一支队伍由n人组成。在潜水时必人组成。在潜水时必 须使用氧气瓶，但是每只队伍只有一个氧气瓶。最多两人同时使用一个氧气须使用氧气瓶，但是每只队伍只有一个氧气瓶。最多两人同时使用一个氧气 瓶，但此时两人必须同步游泳，因此两人达到终点的时间等于较慢的一个人瓶，但此时两人必须同步游泳，因此两人达到终点的时间等于较慢的一个人 单独游到终点所需要的时间。好在大家都很友好，因此任何两个人后都愿意单独游到终点所需要的时间。好在大家都很友好，因此任何两个人后都愿意 一起游水。安排一种潜水的策略，使得最后一名选手尽量的达到终点。一起游水。安排一种潜水的策略，使得最后一名选手尽量的达到终点。 输入：输入： 第一行：队伍的人数第一行：队伍的人数n（=1000）。）。 第二行：第二行：n个数，分别是个数，分别是n个人潜水所用的时间个人潜水所用的时间ti(=1000)。