C++实现自顶向下的归并排序算法.docx

C++实现自顶向下的归并排序算法C++实现自顶向下的归并排序算法自顶向下的归并排序算法是采用分治法进行自顶向下的程序设计方式，下面小编为大家整理了C++实现自顶向下的归并排序算法，希望能帮到大家！一.算法描述自顶向下的归并排序：采用分治法进行自顶向下的程序设计方式，分治法的核心思想就是分解、求解、合并。1.先将长度为N的无序序列分割平均分割为两段2.然后分别对前半段进行归并排序、后半段进行归并排序3.最后再将排序好的前半段和后半段归并过程(2)中进行递归求解，最终下图详细的分解了自顶向下的.合并算法的实现过程：二.算法实现/*=============================================================================##FileName:mergeSort.c#Algorithm:归并排序(自顶向下)#Author:Knife#Created:2014-06-1416:40:02#=============================================================================*/#include#includevoidmerge_sort(int*intArr,intintArr_len);voidmerge_array(int*intArr1,intlen1,int*intArr2,intlen2);voidmain(){intintArr[]={8,3,6,4,2,9,5,4,1,7};intn=sizeof(intArr)/sizeof(intArr[0]);inti=0;merge_sort(intArr,n);for(;i1){int*intArr1=intArr;intintArr1_len=intArr_len/2;int*intArr2=intArr+intArr_len/2;intintArr2_len=intArr_len-intArr1_len;//分别归并排序merge_sort(intArr1,intArr1_len);merge_sort(intArr2,intArr2_len);//排序merge_array(intArr1,intArr1_len,intArr2,intArr2_len);}}//合并两个数组，并排序voidmerge_array(int*intArr1,intlen1,int*intArr2,intlen2){//申请分配空间int*list=(int*)malloc((len1+len2)*sizeof(int));inti=0,j=0,k=0;while(i<len1&&j<len2){//把较小的那个数据放到结果数组里，同时移动指针list[k++]=(intArr1[i]<intArr2[j])?intArr1[i++]:intArr2[j++];}//如果intArr1还有元素，把剩下的数据直接放到结果数组while(i<len1){list[k++]=intArr1[i++];}//如果intArr2还有元素，把剩下的数据直接放到结果数组while(j<len2){list[k++]=intArr2[j++];}//把结果数组copy到intArr1里for(i=0;i<k;i++){intArr1[i]=list[i];}//释放申请的空间free(list);}三.算法分析平均时间复杂度：O(nlog2n)空间复杂度：O(n)(用于存储有序子序列合并后有序序列)稳定性：稳定