排序-归并排序

排序思路：递归地对两个已排序的子序列进行比较，然后逐一的导入到另一个序列中。

补充：我们需要将原序列不断地一分为二，然后进行排序，同时需要注意比较的序列长度。如果每次都创造一块空间来存放序列则会造成操作的冗余，所以我们只一次性开辟一个与原序列等长的数组空间，并通过指针的改变对这块空间进行访问。

优点：时间复杂度为 强-NlogN

缺点：对指针的操作麻烦，若用递归实现会占用系统的堆栈，算法复杂，一般内排序不使用。

自己的代码实现先欠着，偷一下官方的

*归并排序-递归实现*/
/* L=左边起始位置，R=右边起始位置，RightEnd =右边终点位置*/
void Merge( ElementType A[]， ElementType TmpA[]， int L，int R, int RightEnd )
{ /*将有序的A[L] A[R- 1]和A[R] "A[RightEnd]归并成一个有序序列 */
int LeftEnd, NumElements, Tmp:
int i:
LeftEnd = R - 1: /*左边终点位置*/
Tmp = L:
/*有序序列的起始位置*/
NumElements = RightEnd - L + 1:
while( L <= LeftEnd 8& R <= RightEnd ) {
if(A[L]<=A[R])
TmpA[Tmp++] =
A[L++]: /*将左边元素 复制到TmpA */
else
TmpA[Tmp++] = A[R++]: /*将右边元素复制到TmpA */
while( L <= LeftEnd )
TmpA[Tmp++] = A[L++]: /*直接复制左边剩下的*/
while( R <= RightEnd )
TmpA[Tmp++] = A[R++]: /*直接复制右边剩下的 */
for( i = 0: i < NumElements; i++， RightEnd -- )
A[RightEnd] = TmpA [RightEnd]: /*将有序的TmpA[]复制回A[] */
void Msort( ElementType A[]， ElementType TmpA[]， int L，int RightEnd )
{ /*核心递归排序函数 */
int Center ;
if(L Center = (L+RightEnd) / 2:
Msort( A
TmpA, L, Center )
/*递归解决左边*/
Msort(.
TmpA, Center+1,
RightEnd ):
/* 递归解决右边 */
Merge( A, ImpA, L, Center+1, RightEnd ): /* 合并两段有序序列 */

}
void MergeSort( 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( ”空间不足”):
}
 

/*归并排序-循环实现*/
*这里Merge函数在递归版本中给出 */
/* length =当前有序子列的长度*/
void Merge_ pass( ElementType A[],
ElementType TmpA[]， int N, int length )
{ /*两两归并相邻有序子列 */
int i， j;
for ( i=0; i <= N- 2*1ength;
2*1ength )
Merge( A, TmpA, i,
i+length, i+2*1ength-1 );
if
( i+length < N ) /* 归并最后2个子列*/
Merge( A, TmpA, i， i+1ength, N-1) ;
else /
最后只剩1个子列*/
for(j=i;j }
void Merge_ Sort( ElementType A[]， int N )
int 1ength;
ElementType *TmpA;
length = 1; /* 初始化子序列长度*/
TmpA = ma11oc( N * sizeof( ElementType ) ) ;
if ( TmpA != NULL ){
while( 1ength
N)
Merge_ pass( A, TmpA, N, length );
1ength *= 2
Merge_ pass( TmpA, A, N, length );
1ength *= 2
free( TmpA )
}
else printf( ” 空间不足”);
}