归并排序及其适用范围

本文主要是介绍归并排序及其适用范围，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

归并排序的运行时间是O(NlogN)，但它很难用于主存排序，主要问题在于合并两个排序的表需要线性附加的内存，而且还需要讲述据拷贝到临时数组仔拷贝回来这样的附加工作，严重地放慢了排序速度。归并排序一般会用在外部排序的算法中。

void Merge(int A[], int TmpArray[], int Lpos, int Rpos, int RightEnd)
{int i, LeftEnd, NumElements, TmpPos;LeftEnd = Rpos - 1;TmpPos = Lpos;NumElements = RightEnd - Lpos + 1;while(Lpos <= LeftEnd && Rpos <= RightEnd){if(A[Lpos] <= A[Rpos])TmpArray[TmpPos++] = A[Lpos++];elseTmpArray[TmpPos++] = A[Rpos++];}while(Lpos <= LeftEnd)TmpArray[TmpPos++] = A[Lpos++];while(Rpos <= RightEnd)TmpArray[TmpPos++] = A[Rpos++];for(i = 0; i < NumElements; i++, RightEnd--)A[RightEnd] = TmpArray[RightEnd];}void MSort(int A[], int TmpArray[], int Left, int Right)
{int Center;if(Left < Right){Center = (Left + Right)/2;MSort(A, TmpArray, Left, Center);MSort(A, TmpArray, Center+1, Right);Merge(A, TmpArray, Left, Center + 1, Right);}
}void Mergesort(int A[], int N)
{int *TmpArray;TmpArray = (int *)malloc(N * sizeof(int));if( TmpArray != NULL){MSort(A, TmpArray, 0, N-1);free(TmpArray);}else{return;}
}

这篇关于归并排序及其适用范围的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---