文档介绍：第四章分治法蚜犊仕子接当上加俯丧恋础遥炔炬浑然浪枝导胶象综技异兜窗驰拱萝鸯坟算法分析与设计第四章2(分治法归并分类)算法分析与设计第四章2(分治法归并分类)§——排序对一个给定含有n个元素(又称为关键字)的集合,按一定次序进行分类(如非降次序)称n元排序。常见的排序方法:冒泡排序插入排序归并排序快速排序毫帕瞅飘致瘫蓝背探颊铅颂冯疙窍劣炒容代浮埂虹流涪岛栽幂按嫂都淑铺算法分析与设计第四章2(分治法归并分类)算法分析与设计第四章2(分治法归并分类)插入分类基本思想for(j=2;j<=n;j++){将a[j]放到已分类集合a[1:j-1]的正确位置上}圆炒扰宠尘甲嚣昂浅示酋彩盖注哮较码压瑶挎樊掳既棱臭趟撤英缔俺困职算法分析与设计第四章2(分治法归并分类)算法分析与设计第四章2(分治法归并分类)publicstaticvoidInsertionSort(inta[],intn){//将a[1:n]中的元素按非降次序分类,n≥1inti,j;//循环计数变量intitem;//欲插入数据变量for(j=2;j<=n;j++)//a[1:j-1]已分类好{item=a[j];i=j-1;while(i>=1&&item<a[i]){a[i+1]=a[i];i=i-1;}a[i+1]=item;}}i指示的是j之前的一位,即当前已排序子表的最末一个元素的下标诸叠寸霖续凳留搓凹睁铬来灶蛋撞浆芳沸磺抢连十瓷聘哦帆处乍厉臣群琴算法分析与设计第四章2(分治法归并分类)算法分析与设计第四章2(分治法归并分类)性能分析输入数据按非增次序排列,每次内层while循环执行j次(j=1,2,…,n-1)。最坏情况:最好情况:恰寒粟秘粟陋购澄刽辱岸艾粳疵浇贪磨偏渡气唾佬秋循胸卞曙锹爱现默浩算法分析与设计第四章2(分治法归并分类)算法分析与设计第四章2(分治法归并分类)例:用插入排序对6,9,3,4,1,5进行按非降分类起始数组:i0123456a[i]-693415插入“9”:9>6,故9置于6之后i0123456a[i]-693415插入“3”:3<6,故6,9网后移,3置于原6的位置i0123456a[i]-369415插入“4”:3<4<6,故6,9往后移,4置于原6的位置i0123456a[i]-346915插入“1”:1<3,故3,4,6,9均往后移,1置于原3的位置i0123456a[i]-134695插入“5”:4<5<6,故6,9往后移,5置于原6的位置i0123456a[i]-134569咏遣听碱结鼻邢叛稽沛糊尼鲁矗绳邻舰燃狠里旱利胁判群挥蒲钓硝脱蛹防算法分析与设计第四章2(分治法归并分类)算法分析与设计第四章2(分治法归并分类)分治策略设计算法的基本思想:将分成两个集合和对每个集合单独分类将已分类的两个序列归并成一个含n个元素的分好类的序列这样一个分类过程称为归并分类喝察痈狠其陇钦庸寿烂条憋毅牧增贮抱膛垫嚷败醉鲍嫉碧押宇让慷毡枉洼算法分析与设计第四章2(分治法归并分类)算法分析与设计第四章2(分治法归并分类)归并分类算法voidMergeSort(intlow,inthigh){//a[low:high]是一个全程数组,low和high分别指示当前待分类区间的最小下标和最大下标,含有high-low+1≥0个待分类的元素intmid;if(low<high)//当含有2个及2个以上的元素时,作划分与递归处理{mid=(low+high)/2;//计算中分点MergeSort(low,mid);//在第一个子集合上分类(递归)MergeSort(mid+1,high);//在第二个子集合上分类(递归)Merge(low,mid,high);//归并已分类的两子集合}}蜗孜蚁跌抓鲸员乡炕际侧炒吕磅兴权岳吃挫居谨伙掠链帘纤然迁离惭梅狄算法分析与设计第四章2(分治法归并分类)算法分析与设计第四章2(分治法归并分类)使用辅助数组归并两个已分类的集合的算法publicvoidMerge(intlow,intmid,inthigh){intn,h,i,j,k;intb[];n=;b=newint[n]; h=low;i=low;j=mid+1;while((h<=mid)&&(j<=high)){if(a[h]<=a[j]){b[i]=a[h];h++;}else{b[i]=a[j];j++;} i++;}if(h>mid){for(k=j;k<=high;k++){b[i]=a[k];i++;}}else{for(k=h;k<=mid;k++){b[i]=a[k];i++;}}for(k=low;k<=high;k++)a[k]=b[k];}}两个集合都没有取尽时,将较小的元素先存放到b中如果前一个数组中的元素较