摘 要:排序(Sorting)是计算机程序设计中的一个重要操作,它的功能是将一个数据记录的任意序列,重新排列成一个按关键字有序的序列,在实现的过程中,可以有多种方法,其中利用分治策略是解决这一问题的有效途径。本文通过比较讨论了运用分治策略的思想实现快速求解,证明其有效性和高效性。
　　关键词:分置策略;应用;分析
　　
　　1前言
　　
　　任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算。n=2时,只要作一次比较即可排好序。n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。
　　
　　2分治策略的应用与分析
　　
　　分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
　　分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
　　分治法在每一层递归上都有三个步骤:
　　①分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
　　②解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;
　　③合并:将各个子问题的解合并为原问题的解。
　　我们以线性表查找为例,
　　例:在线性表L中找出最大数 {1,5,13,6,8,9,215,3}
　　(1)、用常规查找法,就是一个一个的扫描L的所有元素,找出最大数和最小数。
　　int maxmin(int a[])
　　{int max1=a[0],min1=a[0];
　　 for(i=1;i　　{if (max1>a[i])max1=a[i];
　　if (max1　　}
　　}
　　我们分析这种查找方式:需要14次比较,算法复杂度:T(n)=O(n);
　　(2)、用递归分治策略查找法
　　算法的实现(C语言):
　　//主函数
　　#include
　　void maxmin(int i,int j,int a[]);
　　int max,min; //全局变量
　　void main()
　　{
　　 int a[]={1,5,13,6,8,9,215,3,66,8};
　　 max=a[0];
　　 min=a[0];
　　 maxmin(0, sizeof(a)/sizeof(a[0])-1,a);
　　 cout<　　 cout<　　}
　　//函数如下
　　void maxmin(int i,int j,int a[])
　　{
　　 if (j-i>1)//子集大于二时候,分集
　　 {
　　 maxmin(i,int((j+i)/2),a);
　　 maxmin(int((j+i)/2)+1,j,a);
　　 }
　　 else
　　 {
　　 if (a[i]>a[j])
　　 {
　　if (max　　 if (min>a[j]) min=a[j];
　　 }
　　 else
　　{
　　if (max　　 if (min>a[i]) min=a[i];
　　}
　　 }
　　}
　　分析:我们可以把10个元素分成 A1={1,5,13,6}和A2={8,9,215,3}两组,分别求出两组的最大最小值,然后比较这两组的最大最小值,求出全部元素的最大值。
　　如果A1和A2中的元素多于两个,则再用上述方法将其分为两子集,直到集合中的元素少于二个为止。
　　
　　我们分析这种查找方式:图中每个方框中,左边是最小值,右边是最大值。从图中看出,用这种方法一共比较了10次,比直接比较法的14次减少4次,即约减少了1/3。
　　我们以在8个元素中找出最小数和最大数做比较
　　
　　这种算法在比较数组元素所用时间比比较整数i、j所用的时间多得多时,是一种较优的算法。
　　
　　结语
　　
　　由此可见:利于分治策略求解时,所需时间取决于分解后子问题的个数、子问题的规模大小等因素,而二分法,由于其划分的简单和均匀的特点,是经常采用的一种有效的方法。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便,在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,并由此可产生许多高效算法。
　　
　　参考文献:
　　[1]SARABAASE.计算机算法.设计与分析导论[M](第3版).北京:高等教育出版社,2001.
　　[2]王海源.分治算法的两种思路和形式[J].上海师范大学学报(自然科学版),2003(32) .
　　[3]范时平.基于满二叉树的原地快速排序[J].重庆邮电学院学报(自然科学版),2006(18):781-783.
　　[4]虎治勤.快速排序性能分析[J].电脑知识与技术(学术交流),2007(2):443-444.