归并排序 的递归算法

时间:2021-10-11 04:13:49


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,实现排序。