分治算法策略

《分治算法策略》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、分治算法策略（2）快速排序改进算法（1）基本思想：与方法1相比，主要做了以下改进，取无序区R[1..HJ中间的一个数x作为比较基准,从左扫描找到比x人的数R[i],从右扫描找到比x小的数R[j],然后交换R[i]和R[j],直到i>j,一趟排序结束，此时R[l..j]的元素均小于（2）排序过程：初始关键字[3865974976132749]第一次交换后[3849974276132165J第二次交换后[3849274276B9765J第三次交换示[3849271376499765],此时i=5,j=4,i>j第一趟排序结束[3849271376499765]【示例】:初始关键字一趟排

2、序之示[3865974976132749J[38492713][76499765]二趟排序之后三趟排序Z后[381327][49][49][769765][13][3827][49][49][7665][97]最后的排序结果[13][27]L38J[49][49J[65][76]L97]快速排序算法qsortproceduresort(l,r:longint);tmpjj,mid:longint;beginj:=r;mid:=a[(i+j)div2];repeatwhilea[i]

3、whileafjl>middodec(j);｛在右半部分寻找比屮间数小的数｝ifi<=jthen｛若找到一组与排序目标不一致的数对则交换它们｝begintmp:=a[i];a[i]:=a[j];a[j]:=tmp;inc(i);dec(j);｛继续找｝untili>j;｛注意这里不能有等号｝ifl

4、键字有序或基木有序时，快速排序将退化为冒泡排序，其时间复杂度为0(nJ)o如果我们选择标准关键字时采取一定的策略，就可以避免快速排序的退化，比如我们随机产生一个值x,以序列中的第x个位置的记录的关键字作为标准关键字，这样的随机化快速排序能很好地防止退化。一般都以序列中间位置的记录的关键字作为标准关键字，这样既可能简化代码，乂能防止退化，是一•种折屮的常用方法。从时间上看，快速排序的平均性能优于前面讨论过的冒泡排序，选择排序、插入排序列方法，但快速排序需要一个栈空间来实现递归。上机练习：(本次练习要求用文件操作，提交源程序评测)众数(masses.pas)【问题描述】由文件给出N个1

5、到30000间无序数正整数，其屮1WNW10000,同一个正整数可能会出现多次，出现次数最多的整数称为众数。求出它的众数及它出现的次数。【输入格式】输入文件第一行是正整数的个数N,第二行开始为N个正整数。【输出格式】输出文件有若干行，每行两个数，第1个是众数，第2个是众数出现的次数。【输入样例】masses.in12242325372343【输出样例】masses.out24342、军事机密(secret.pas)【问题描述】军方截获的信息由n(n〈二30000)个数字组成，因为是敌国的高端秘密，所以一时不能破获。授原始的想法就是对这n个数进行小到大排序，每个数都对应一个序号，然后

6、对第i个是什么数感兴趣，现在要求编程完成。【输入格式】第一行n,接着是n个截获的数字，接着一行是数字k,接着是k行要输出数的序号。【输出格式】k行序号对应的数字。【输入样例】secret.in5121112612373243【输出样例】secret,out71231213.NOIP2007TG_1_统计数字(count.pas)【问题描述】某次科研调査时得到了n个自然数,每个数均不超过1500000000(1.5*10^9)。已知不相同的数不超过10000个，现在需要统计这些H然数各H出现的次数，并按照H然数从小到人的顺序输出统计结果。【输入】输入文件count,in包含n+1行;

7、第一行是整数n,表示自然数的个数；第2~n+l每行一个自然数。【输出】输出文件count,out包含m行(m为n个自然数中不相同数的个数)，按照自然数从小到大的顺序输出。每行输出两个整数，分别是白然数和该数出现的次数，其间用一个空格隔开。【输入输岀样例】count,in8242451002100count,out］2342511002【限制】40%的数据满足：1<二*二100080%的数据满足：1〈二*二50000100%的数据满足：l<=n<=200000,每个数均