第2讲 排序算法及应用

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 i ,a i+1,ana i ,a i+1,

2、an中最小的数与中最小的数与a i a i 交换位置，这交换位置，这样经过第样经过第i i遍处理后，遍处理后，aiai是所有的中的第是所有的中的第i i小。即前小。即前i i个数就已经排个数就已经排好序了。好序了。N-1N-1遍处理后，剩下的最后一个一定是最大的，不需要再处理了。遍处理后，剩下的最后一个一定是最大的，不需要再处理了。排序的关键字：排序的关键字：20 30 10 15 16 13 8第第i个和后边的依次比较，找最小的放在个和后边的依次比较，找最小的放在i处。处。a:待排序的数组；待排序的数组；/从小到大排序从小到大排序简单选择排序：简单选择排序：for i:=1 to n-1 d

3、o 从第一个元素开始从第一个元素开始,进行进行n-1遍处理遍处理 for j:=i+1 to n do 第第i遍处理遍处理 If aiaj then 交换交换ai和和aj begin t:=ai; ai:=aj; aj:=t; end; /简单选择排序简单选择排序:从小到大从小到大const maxn=1000;var n,i,j,t:integer; a:array1.maxn of integer;begin randomize; /随机过程初始化随机过程初始化 readln(n); for i:=1 to n do ai:=random(1000); /产生产生n个个0,999之间的整数

4、。之间的整数。 for i:=1 to n-1 do for j:=i+1 to n do if aiaj then begin t:=ai; ai:=aj; aj:=t; end; for i:=1 to n-1 do write(ai, ); writeln(an);end.算法的改进算法的改进: 减少交换次数减少交换次数排序的关键字：排序的关键字：20 30 10 15 16 13 8 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; a

5、i:=t; end; end;2、冒泡排序算法：、冒泡排序算法：基本思想基本思想：（从小到大排序）：（从小到大排序） 将待排序的数据看作竖派排的一列将待排序的数据看作竖派排的一列”气泡气泡“，小的数据，小的数据比较轻，从而要上浮。比较轻，从而要上浮。共进行共进行n-1遍处理，每一遍处理，就是从底向上检查序列，遍处理，每一遍处理，就是从底向上检查序列，如果如果相邻相邻的两个数据顺序不对，即轻（小）的在下面，就交的两个数据顺序不对，即轻（小）的在下面，就交换他们的位置。换他们的位置。 第一遍处理完后，第一遍处理完后，“最轻最轻”的就浮到上面。的就浮到上面。 第二遍处理完后，第二遍处理完后，“次轻次

6、轻”的就浮到上面。的就浮到上面。 共需要共需要n-1遍处理即完成排序。遍处理即完成排序。排序的关键字：从小到排序的关键字：从小到大大20 30 10 15 16 13 8/ 简单的冒泡排序简单的冒泡排序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;算法的改进算法的改进关键字关键字 20 30 40 50 60 10/ 判断标志：判断标志： flag=true 已有序已有序/改进后的冒泡排序改进后的冒泡排序for i:=1 to n-1 do begin f

7、lag:=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;3、插入排序算法、插入排序算法:基本思想：基本思想：经过经过i-1i-1遍处理后，遍处理后，a1,a2,ai-1a1,a2,ai-1已排好序。已排好序。第第i i遍处理是将元素遍处理是将元素aiai插入到插入到a1,a2,ai-1a1,a2,ai-1的适当的位置，从的适当的位

8、置，从而使得而使得a1,a2,ai-1,aia1,a2,ai-1,ai又是排好的序列。又是排好的序列。排序的关键字：从小到排序的关键字：从小到大大20 30 10 15 16 13 8a:array0.n of integer; a:array0.n of integer; a0a0记录当前待插元记录当前待插元aiaifor i:=2 to n dofor i:=2 to n do begin begin a0:=ai; a0:=ai; 取第取第i i个元素作为待插入元素个元素作为待插入元素 j:=i-1; j:=i-1; 从已排好的最后一个从已排好的最后一个ai-1ai-1开始比较开始比较

9、while a0aj do / while a0aj do / 找找j j满足：满足： aj=a0aj+1aj=a0=aja0=aj时循环结束时循环结束 aj+1:=a0; aj+1:=a0; 在第在第j+1j+1个位置插入个位置插入aiai元素元素 end; end;4、快速排序算法：、快速排序算法： 基本思想：把待排序的基本思想：把待排序的n个元素放到一个中的任一个元素数组中，先个元素放到一个中的任一个元素数组中，先取数组取数组中的某一个元素作为一个基准元素中的某一个元素作为一个基准元素，把这个元素放到数组中合适的位置，同时，把这个元素放到数组中合适的位置，同时对其他元素进行调整，使得在这

10、个基准元素的右边的所有元素都比这个基准元对其他元素进行调整，使得在这个基准元素的右边的所有元素都比这个基准元素大，而基准元素左边的元素都比它小。也就是说，这个基准元素当前所在的素大，而基准元素左边的元素都比它小。也就是说，这个基准元素当前所在的位置就是排序后的最终位置。然后再对基准元素的前后两个区间分别进行快速位置就是排序后的最终位置。然后再对基准元素的前后两个区间分别进行快速排序，直到每个区间为空后者只有一个元素时，整个快速排序结束。排序，直到每个区间为空后者只有一个元素时，整个快速排序结束。方法：方法： 取数组中的取数组中的第一个第一个元素作为基准元素：元素作为基准元素： 把待排序的数组按

11、照基准元素分为左右两部分的过程称为快速排序的一次把待排序的数组按照基准元素分为左右两部分的过程称为快速排序的一次划分（一趟排序）。划分（一趟排序）。 待排数组：待排数组：a1 an。一次划分的过程：一次划分的过程：设设I，j两个指针，开始时，两个指针，开始时，i 1，j n，x ai：基准元素。如果：基准元素。如果aj=x 那么那么j j-1，直到找到，直到找到ajx，然，然后：后：aj ai。35 12 37 15 40 31 50 30 29 6035 12 37 15 40 31 50 30 29 606 629 12 30 15 31 35 50 40 37 603 315 12 29

12、 30 31 35 50 40 37 602 212 15 29 30 31 35 50 40 37 604 412 15 29 30 31 35 50 40 37 609 912 15 29 30 31 35 37 40 50 607 712 15 29 30 31 35 37 40 50 6012 15 29 30 31 35 37 40 50 60procedure qsort(s,t:integer);s:待排序数组首元素下标待排序数组首元素下标,t:末尾元素下标末尾元素下标 var i,j:integer; x:integer; begin i:=s; j:=t; x:=as; x:

13、首元素为基准元素首元素为基准元素 while i=x) and(ji) do dec(j); 从未尾找比从未尾找比x小的元素小的元素aj if ij 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 qs

14、ort(s,i-1); 对基准元素对基准元素x的的左左区间再进行快速排序区间再进行快速排序 if (i+1)t then qsort(i+1,t); 对基准元素对基准元素x的的右右区间再进行快速排序区间再进行快速排序 end;主程序的调用主程序的调用: qsort(1,n);const maxn=10000;/快速排序源程序快速排序源程序var a:array1.maxn of integer; n,i:integer; procedure qsort(l,r:integer); var i,j:integer; x:integer; begin i:=l; j:=r; x:=al; whil

15、e i=x) and(ji) do dec(j); if ij then begin ai:=aj; inc(i); end; while (aii) do inc(i); if ij then begin aj:=ai; dec(j); end; end; ai:=x; /i=j if l(i-1) then qsort(l,i-1); if (i+1)r then qsort(i+1,r); end;begin randomize; readln(n); for i:= 1 to n do ai:=random(100); for i:=1 to n-1 do write(ai, ); w

16、riteln(an); qsort(1,n); for i:=1 to n-1 do write(ai, ); writeln(an);end.排序算法的应用排序算法的应用1、排队接水、排队接水 有有n个人排队在一个水笼头前接水，每个人的接水时间个人排队在一个水笼头前接水，每个人的接水时间互不相等。找出一种互不相等。找出一种n个人排队接水的顺序，使他们平均等个人排队接水的顺序，使他们平均等待的时间最短。待的时间最短。输入：输入： 第一行：第一行：n(tj then begin tem:=ti; ti:=tj; tj:=tem; tem:=numi; numi:=numj; numj:=tem;

17、 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口井的油田。口井的油田。从每口井中都有一条喷油管沿最短路径与主管道直接相连从每口井中都有一条喷油管沿最短路径与主管道直接相连（或南或北

18、）。（或南或北）。 给定各个井的给定各个井的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:=i+1 downto n do if yiy

19、j then begin k:=yi; yi:=yj; yj:=k; end; if n mod 2=1 then write(y(n+1) div 2) 输出中间值 else write(yn div 2, ,y n div 2+1); 输出中间区间 end.3、区间合并、区间合并【问题描述：】【问题描述：】从键盘上任意输入从键盘上任意输入n个区间，然后按从小到大的顺序依次输出个区间，然后按从小到大的顺序依次输出n个区间个区间的并集。的并集。【输入：】【输入：】第一行，区间个数第一行，区间个数n（=1000）以下以下n行，每行两个整数行，每行两个整数a、b（-1000000000ab1000

20、000000）,相相应区间的坐标，中间应区间的坐标，中间一个空格。一个空格。【输出：】【输出：】 n个区间的并集，个区间的并集，n行，每行一个区间，坐标轴的左边的区间先输出。行，每行一个区间，坐标轴的左边的区间先输出。【样例输入：】【样例输入：】32 51 47 8 【样例输出：】【样例输出：】1 57 8区间的合并区间的合并注意：注意：1 1、区间个数、区间个数n n的范围（的范围（=1000=1000）2 2、区间的数据类型和范围：、区间的数据类型和范围： 整数类型、整数类型、-10-109 9-10-109 9算法一：离散化算法一：离散化思路：思路： 设设fi:0.1,fi:0.1,初始

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

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

23、l=aI,2)Tail=aI,2Tail=aI,2If tailaI,1If tailaI,1Writeln(tail);Writeln(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=ai,2) /2 if (ai,1=tail)and(tail=ai,2) /2 then tail:=ai,

24、2; then tail:=ai,2; if tailai,1 then /3 if tailaj,1 then begin t:=ai; ai:=aj; aj:=t; end; end;procedure main; var i:integer; tail:longint; begin assign(output,fout);rewrite(output); write(a1,1, ); tail:=a1,2; for i:=2 to n do begin if (ai,1=tail)and(tail=ai,2) then tail:=ai,2; if tailai,1 then begin

25、 writeln(tail); write(ai,1, ); tail:=ai,2; end; end; writeln(tail); close(output); end;/主程序主程序begin init; main;end.4、潜水比赛、潜水比赛 在马其顿王国举行了一次潜水比赛。其中一个项目是从高山上跳下在马其顿王国举行了一次潜水比赛。其中一个项目是从高山上跳下水，再潜水达到终点。这是一个团体项目，一支队伍由水，再潜水达到终点。这是一个团体项目，一支队伍由n人组成。在潜水时必人组成。在潜水时必须使用氧气瓶，但是每只队伍只有一个氧气瓶。最多两人同时使用一个氧气须使用氧气瓶，但是每只队伍只有

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

27、样例：输入：输入：31 3 4输出：输出：8分析分析:先从简单入手先从简单入手:1) n=2 ,时间时间 t: 1 10 所需的时间为所需的时间为:102) n=3, 时间时间 t: 1 3 4所需的时间为所需的时间为:3+1+4=83) n=4 ,时间时间 t: 1 10 11 12 所需的时间为所需的时间为:10+1+11+1+12=35贪心策略方法一贪心策略方法一: N个人个人: 每个人所需的时间每个人所需的时间: t1，t2，tn。假设。假设t1最小。最小。 每次由每次由t1接送人和氧气瓶，则接送人和氧气瓶，则总时间：总时间：s=t2+t3+。tn+（n-2）*t14）n=4 ，每个人

28、所用时间：，每个人所用时间：1 2 5 8采用 贪心策略方法一：贪心策略方法一：计算所用的总时间为：计算所用的总时间为：2+5+8+1*2=17事实上：采用下面策略：事实上：采用下面策略：第一步：第一步： 1 2一起先过，一起先过， 用时：用时：2第二步：第二步： 1 送回氧气瓶，送回氧气瓶， 用时：用时：1第三步：第三步： 5 8一起过，一起过， 用时：用时： 8第四步：第四步： 2送回氧气瓶，送回氧气瓶， 用时：用时：2第五步：第五步： 1 和和2一起过去，一起过去， 用时：用时：2 完成。完成。 共用时：共用时：2+1+8+2+2=15y then 用用t1送送 else 用用t1和和t

29、2送送贪心三算法：贪心三算法：数组数组a存时间：存时间：把时间从小到大排序。把时间从小到大排序。sum:=0; if odd(n) then begin sum:=sum+a2+a1+a3 end else sum:=sum+a2; i:=n; while i3 do begin x:=2*a2+a1+ai; 用用a1和和a2送一趟送一趟 y:=2*a1+ai+ai-1; 用用a1送一趟送一趟 if xy then sum:=sum+x else sum:=sum+y; dec(i,2); i=i-2:每趟送两人每趟送两人 end; writeln(sum);1、成绩排名、成绩排名【问题描述：

30、】【问题描述：】根据期末考试的成绩单信息，把所有的学生按总分从高到低的顺序输出。根据期末考试的成绩单信息，把所有的学生按总分从高到低的顺序输出。【输入：】【输入：】第一行：学生的个数第一行：学生的个数n（n=100）。）。以下以下n行：每行包含一个学生的信息，依次是：学号（行：每行包含一个学生的信息，依次是：学号（1.n）、姓名、语文）、姓名、语文成绩、数学成绩。他们中间有且仅有一个空格隔开，输入信息中没有多余的成绩、数学成绩。他们中间有且仅有一个空格隔开，输入信息中没有多余的空格。姓名全是字母，长度不大于空格。姓名全是字母，长度不大于200，各科成绩不超过，各科成绩不超过100。【输出：】【输出：】N行，每行包含一个学生的信息：学号、姓名、总分。中间用一个空格隔开，行，每行包含一个学生的信息：学号、姓名、总分。中间用一个空格隔开，不能有多余的空格。总分相同的学生，学号大的在