第6讲排序算法及应用

第六讲排序算法及应用刘建国昌邑市卜庄初中排序算法的种类：1、选择排序2、冒泡排序3、插入排序4、快速排序5、堆排序1、选择排序算法基本思想：

对待排序的序列进行n-1遍处理：第1遍处理是从a[1],a[2],……a[n]中选择最小的放在a[1]位置；第2遍处理是从a[2],a[3],……a[n]中选择最小的放在a[2]位置；……第I遍处理是将a[i],a[i+1],……a[n]中最小的数与a[i]交换位置，这样经过第i遍处理后，a[i]是所有的中的第i小。即前i个数就已经排好序了。N-1遍处理后，剩下的最后一个一定是最大的，不需要再处理了。

a:待排序的数组；//从小到大排序简单选择排序：

fori:=1ton-1do{从第一个元素开始,进行n-1遍处理}

forj:=i+1tondo{第i遍处理}

Ifa[i]>a[j]then{交换a[i]和a[j]}

begint:=a[i];a[i]:=a[j];a[j]:=t;end;

算法的改进:减少交换次数fori:=1ton-1dobegink:=i;forj:=i+1tondoifa[j]<a[k]thenk:=j;ifk<>ithenbegint:=a[k];a[k]:=a[i];a[i]:=t;end;end;排序的关键字：20301015161382、冒泡排序算法：基本思想：（从小到大排序）将待排序的数据看作竖派排的一列”气泡“，小的数据比较轻，从而要上浮。共进行n-1遍处理，每一遍处理，就是从底向上检查序列，如果相邻的两个数据顺序不对，即轻（小）的在下面，就交换他们的位置。第一遍处理完后，“最轻”的就浮到上面。第二遍处理完后，“次轻”的就浮到上面。共需要n-1遍处理即完成排序。//简单的冒泡排序fori:=1ton-1doforj:=ndowntoi+1doifa[j]<a[j-1]thenbegint:=a[j];a[j]:=a[j-1];a[j-1]:=t;end;//判断标志：flag=true已有序//改进后的冒泡排序fori:=1ton-1dobeginflag:=true;forj:=ndowntoi+1doifa[j]<a[j-1]thenbegint:=a[j];a[j]:=a[j-1];a[j-1]:=t;flag:=false;end;ifflag=truethenbreak;//某一轮没有交换，说明都已经有序了end;算法的改进关键字203040506010测定时间的方法：通过访问MemL[Seg0040:$006C]来获取当前时间，它返回的是当日零时到现在所经过的时间，单位约为55毫秒（约1/18.2秒）。测定<语句组2>执行的时间Starttime,endtime:longint;Starttime:=MemL[Seg0040:$006C];<语句组2>endtime:=MemL[Seg0040:$006C];Writeln((endtime-starttime)/18.2:0:2);语句组2运行的时间或：Writeln((MemL[Seg0040:$006C]-starttime)/18.2:0:2);StartTime:=MemL[Seg0040:$006C];fori:=1ton-1doforj:=ndowntoi+1doifa[j]<a[j-1]thenbegint:=a[j];a[j]:=a[j-1];a[j-1]:=t;end;writeln((MemL[Seg0040:$006c]-StartTime)/18.2:0:2);3、插入排序算法:基本思想：经过i-1遍处理后，a[1],a[2],……,a[i-1]已排好序。第i遍处理是将元素a[i]插入到a[1],a[2],……,a[i-1]的适当的位置，从而使得a[1],a[2],……,a[i-1],a[i]又是排好的序列。a:array[0..n]ofinteger;{a[0]记录当前待插元a[i]}fori:=2tondobegina[0]:=a[i];{取第i个元素作为待插入元素}j:=i-1;{从已排好的最后一个a[i-1]开始比较}whilea[0]<a[j]dobegina[j+1]:=a[j];{当待插入元素a[0]小于当前a[j]时，a[j]后移}j:=j-1;end;{当a[0]>=a[j]时循环结束}a[j+1]:=a[0];{在第j+1个位置插入a[i]元素}end;4、快速排序算法：基本思想：把待排序的n个元素放到一个中的任一个元素数组中，先取数组中的某一个元素作为一个基准元素，把这个元素放到数组中合适的位置，同时对其他元素进行调整，使得在这个基准元素的右边的所有元素都比这个基准元素大，而基准元素左边的元素都比它小。也就是说，这个基准元素当前所在的位置就是排序后的最终位置。然后再对基准元素的前后两个区间分别进行快速排序，直到每个区间为空后者只有一个元素时，整个快速排序结束。方法一：取数组中的第一个元素作为基准元素：把待排序的数组按照基准元素分为左右两部分的过程称为快速排序的一次划分（一趟排序）。待排数组：a[1]……a[n]。一次划分的过程：设I，j两个指针，开始时，i←1，j←n，x←a[i]：基准元素。如果a[j]>=x那么j←j-1，直到找到a[j]<x，然后a[i]←a[j]，同时i←i+1,找一个a[i]>x，然后：a[j]←a[i]。procedureqsort(s,t:integer);{s:待排序数组首元素下标,t:末尾元素下标}vari,j:integer;x:integer;begini:=s;j:=t;x:=a[s];{x:首元素为基准元素}whilei<jdobeginwhile(a[j]>=x)and(j>i)dodec(j);{从未部找比x小的元素a[j]}ifj>ithenbegina[i]:=a[j];inc(i);end;{把a[j]放在i处,j处空着}while(a[i]<=x)and(i<j)doinc(i);{继续从前边找比x大元素a[i]}ifi<jthenbegina[j]:=a[i];dec(j);end;{把a[i]移动到j位置处,i处空着}end;a[i]:=x;{基准元素x放到合适的i位置}ifs<(i-1)thenqsort(s,i-1);{对基准元素x的左区间再进行快速排序}if(i+1)<tthenqsort(i+1,t);{对基准元素x的右区间再进行快速排序}end;主程序的调用:qsort(1,n);方法二:取中间元素为基准元素的算法:procedureqsort(l,r:integer);vari,j,mid:integer;temp:integer;begini:=l;j:=r;mid:=a[(l+r)div2];{将当前序列在中间位置的数定义为中间数}repeatwhilea[i]<middoinc(i);{在左半部分寻找比中间数大的数}whilea[j]>middodec(j);{在右半部分寻找比中间数小的数}ifi<=jthenbegin{若找到一组与排序目标不一致的数对则交换它们}temp:=a[i];a[i]:=a[j];a[j]:=temp;inc(i);dec(j);{继续找}end;untili>j;ifl<jthenqsort(l,j);{若未到两个数的边界，则递归搜索左右区间}ifi<rthenqsort(i,r);end;{sort}排序算法的应用1、排队接水有n个人排队在一个水笼头前接水，每个人的接水时间互不相等。找出一种n个人排队接水的顺序，使他们平均等待的时间最短。输入：第一行：n(<100).第二行：依次为n个人的接水时间。输出：第一行：所有人的平均等待时间。第二行：接水的顺序。样例：输入：526138输出：8.4031425varnum,t:array[1..100]ofinteger;n,i,j,sum,tem:integer;beginreadln(n);fori:=1tondoread(t[i]);fori:=1tondonum[i]:=i;fori:=1ton-1doforj:=i+1tondoift[i]>t[j]thenbegintem:=t[i];t[i]:=t[j];t[j]:=tem;tem:=num[i];num[i]:=num[j];num[j]:=tem;end;sum:=0;fori:=1tondosum:=sum+(n+1-i)*t[i];writeln(sum/n:0:2);fori:=1ton-1dowrite(num[i],'');writeln(num[n]);end.2、主油管的最优位置Olay教授正在为一家石油公司咨询。该公司正在设计建造一条由东向西的管道，该管道要穿过一个有n口井的油田。从每口井中都有一条喷油管沿最短路径与主管道直接相连（或南或北）。给定各个井的X和Y坐标，Olay教授如何才能选择主管道的最优位置（即使得个喷管长度总和最小的位置）。输入：3233754输出：4varx,y:array[1..100]ofinteger;n,i,j,k,m:integer;beginread(n);{油井个数}fori:=1tondoread(x[i],y[i]);{每个油井的坐标}fori:=1ton-1do{冒泡排序纵坐标：从小到大}forj:=ndowntoi+1doify[j]<y[j-1]thenbegink:=y[j];y[j]:=y[j-1];y[j-1]:=k;end;ifnmod2=1thenwrite(y[trunc((n+1)/2)]){输出中间值}elsewrite(y[trunc(n/2)],‘’,y[trunc(n/2+1)]);{输出中间区间}end.3、成绩排名【问题描述：】根据期末考试的成绩单信息，把所有的学生按总分从高到低的顺序输出。【输入：】第一行：学生的个数n（n<=100）。以下n行：每行包含一个学生的信息，依次是：学号（1..n）、姓名、语文成绩、数学成绩。他们中间有且仅有一个空格隔开，输入信息中没有多余的空格。姓名全是字母，长度不大于200，各科成绩不超过100。【输出：】N行，每行包含一个学生的信息：学号、姓名、总分。中间用一个空格隔开，不能有多余的空格。总分相同的学生，学号大的在前。【样例输入：】43abc40502gd50401wr60604dsd1020【样例输出：】1wr1203abc902gd904dsd304、区间合并【样例输入：】【问题描述：】从键盘上任意输入n个区间，然后按从小到大的顺序依次输出n个区间的并集。【输入：】第一行，区间个数n（<=1000）以下n行，每行两个整数a、b（-1000000000<a<b<1000000000）,相应区间的坐标，中间一个空格。【输出：】n个区间的并集，n行，每行一个区间，坐标轴的左边的区间先输出。【样例输入：】3548【样例输出：】1578区间的合并注意：1、区间个数n的范围（<=1000）2、区间的数据类型和范围：整数类型、-109--109算法一：离散化思路：◆设f[i]:0..1,初始值全部为0。◆每读入一个区间abFori:=1tonForj:=atobdof[j]=1◆最后输出f[j]=1的区间。时间复杂度：1012，只能过部分数据。算法二：直接合并1、按每个区间的左端的的值升序排列。由于N<=1000,任意排序算法。注意数据结构的设置:

◆记录类型

◆二维数组：a:array[1..1000,1..2]oflongint;a:array[1..1000]ofarray[1..2]oflongint2、合并过程◆输出第一个区间的左端点坐标（最小的）◆依次处理后面的n-1的区间。Ifa[I,2]<=tailTail不变If(a[I,1]<=tail)and(tail<=a[I,2])Tail=a[I,2]Iftail<a[I,1]Writeln(tail);Write(a[I,1]);Tail:=a[I,2];write(a[1,1],'');tail:=a[1,2];fori:=2tondobeginif(a[i,1]<=tail)and(tail<=a[i,2])//2thentail:=a[i,2];iftail<a[i,1]then//3beginwriteln(tail);write(a[i,1],'');tail:=a[i,2];end;end;writeln(tail);5、修理牛棚

在一个暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。好在许多牛正在度假，所以牛棚没有住满。有些牛棚里有牛，有些没有。所有的牛棚有相同的宽度,并且一个紧挨着另一个被排成一行。自门遗失以后,农民约翰很快在牛棚门口之前竖立起新的木板。他的新木材供应者将会供应他任何他想要的长度,但是供应者只能提供有限数目的木板。农民约翰想将他购买的木板总长度减到最少。给出可能买到的木板最大的数目M(1<=M<=50)；牛棚的总数S(1<=S<=200)；牛棚里牛的数目C(1<=C<=S)。牛所在的牛棚的编号number(1<=number<=S),计算拦住所有有牛的牛棚所需木板的最小总长度。输出所需木板的最小总长度（每个牛棚的宽度为1）作为的答案。

输入：第1行：MSC（中间用空格分开）第2行到c+1共c行，每行一个个整数，表示牛所占的牛棚的编号。输出：单独的一行包含一个整数，表示所需木板的最小总长度。样例：输入：4501834681415161721252627303140414243输出：25

[提示：一种最优的安排是用板拦住牛棚3-8,14-21,25-31,40-43.]6、潜水比赛

在马其顿王国举行了一次潜水比赛。其中一个项目是从高山上跳下水，再潜水达到终点。这是一个团体项目，一支队伍由n人组成。在潜水时必须使用氧气瓶，但是每只队伍只有一个氧气瓶。最多两人同时使用一个氧气瓶，但此时两人必须同步游泳，因此两人达到终点的时间等于较慢的一个人单独游到终点所需要的时间。好在大家都很友好，因此任何两个人后都愿意一起游水。安排一种潜水的策略，使得最后一名选手尽量的达到终点。输入：第一行：队伍的人数n（<=1000）。第二行：n个数，分别是n个人潜水所用的时间ti(<=1000)。样例：输入：3134输出：8分析:先从简单入手:1)n=2,时间t:110所需的时间为:102)n=3,时间t:134所需的时间为:3+1+4=83)n=4,时间t:1101112所需的时间为:10+1+11+1+12=35贪心策略方法一:N个人:每个人所需的时间:t1，t2，……tn。假设t1最小。每次由t1接送人和氧气瓶，则总时间：s=t2+t3+。。。。tn+（n-2）*t14）n=4，每个人所用时间：1258采用贪心策略方法一：计算所用的总时间为：2+5+8+1*2=17事实上：采用下面策略：第一步：12一起先过，用时：2第二步：1送回氧气瓶，用时：1第三步：58一起过，用时：8第四步：2送回氧气瓶，用时：2第五步：1和2一起过去，用时：2完成。共用时：2+1+8+2+2=15<17贪心策略方法二:将n个人的时间从小到达排序，假设从小到大为：t1，t2，……tn1：t1和t2过：t22：t1带瓶返回：t13：最大的两个人：tnt