首页 > 代码库 > 归并排序 的递归算法
归并排序 的递归算法
void Merge(ElementType A[],ElementType Temp[],int Left,int Right,int RightEnd){ int temp,i, LeftEnd,count; LeftEnd=Right-1;// 超级错误 count=RightEnd-Left+1; temp=Left; while(Left<=LeftEnd&& Right<=RightEnd)//超级错误 { if(A[Left]<=A[Right]) Temp[temp++]=A[Left++]; else Temp[temp++]=A[Right++]; } while(Left<=LeftEnd) Temp[temp++]=A[Left++]; while(Right<=RightEnd) Temp[temp++]=A[Right++]; for ( i = 0; i < count; i++,RightEnd--) A[RightEnd]=Temp[RightEnd];//超级错误 }void (ElementType A[],ElementType Temp[],int Left,int RightEnd){ int center; if(Left<RightEnd) { center=(Left+RightEnd)/2; Msort(A,Temp,Left,center); Msort(A,Temp,center+1,RightEnd); Merge(A,Temp,Left,center+1,RightEnd); }} void M_sort( ElementType A[], int N ){ /* 归并排序 */ ElementType *TmpA; TmpA = (ElementType *)malloc(N*sizeof(ElementType)); if ( TmpA != NULL ) { Msort( A, TmpA, 0, N-1 ); free( TmpA ); } else printf( "空间不足" ); }
错误分析： 1.将LeftEnd=RightEnd-1; 没有想清楚leftend 与right 是相连的。
2.Left<=LeftEnd 错误写成<， 极限情况，只有2个元素的时候，left=0，leftend=0,right=1,right=1;
3.A[RightEnd]=Temp[RightEnd];错误的写成.Temp[RightEnd]=A[RightEnd];
算法分析：
merge 实现2个有序序列的归并。
left 表示第一个有序序列的起始位置，leftend 表示第一个有序序列最后一个元素的下标，right表示第二个有序序列的起始下标，默认leftend与right相邻。
rightend表示第二个序列的最后元素的下标。 temp数组临时存放排序的序列。
当A[Left]<=A[Right]，说明左边序列第一个元素小于右边第一个元素，将左边序列第一个元素放入temp。同时left++,temp++,，继续比较A[Left]<=A[Right]。
当A[Left]>A[Right],反之。
当有一个序列全部放入temp中时，将另一个序列直接复制到temp中。
Msort 递归实现排序。
center将序列分成2组。
递归对两组进行Msort，调用merge，实现排序。
归并排序 的递归算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。