首页 > 代码库 > 排序算法--归并排序
排序算法--归并排序
1.简介
归并算法是递归地将数组分成两个小数组，分别对两个数组进行排序，然后合并两个有序数组，递归的终止条件是要合并的两个数组分别只有一个元素。
合并两个有序数组的算法为：
取两个输入数组A,B和一个输出数组C，以及三个计数器Aptr，Bptr，Cptr，分别指向三个数组的开始位置；
比较A[Aptr]，B[Bptr]，取较小值存入C；
当两个输入表有一个用完时，则将另一个表中剩余部分拷贝到C中。
空间复杂度是O（N），时间复杂度是O（NlogN）
递归排序由于需要线性附加内存，在整个算法中还要花费将数据拷贝到临时数组再拷贝回来的这些附加操作，速度并不理想、
2.实现
void Merge(ElementType A[], ElementType *TmpArray, int Lpos, int Rpos, int RightEnd)
{
int LeftEnd = Rpos - 1;
int TmpNum = RightEnd - Lpos + 1;
int TmpPos = Lpos;
int i = 0;
while (Lpos <= LeftEnd && Rpos <=RightEnd)
{
if (A[Lpos] <= A[Rpos])
{
TmpArray[TmpPos++] = A[Lpos++];
}
else
{
TmpArray[TmpPos++] = A[Rpos++];
}
}
while (Lpos <= LeftEnd)
{
TmpArray[TmpPos++] = A[Lpos++];
}
while (Rpos <= RightEnd)
{
TmpArray[TmpPos++] = A[Rpos++];
}
/* Copy TmpArray back */
for (i = 0; i < TmpNum; i++,RightEnd--)
{
A[RightEnd] = TmpArray[RightEnd];
}
}
void MSort(ElementType A[], ElementType TmpArray[], int Left, int Right)
{
int Center = (Left + Right) / 2;
if (Left < Right)
{
MSort(A, TmpArray, Left, Center);
MSort(A, TmpArray, Center + 1, Right);
Merge(A, TmpArray, Left, Center + 1, Right);
}
}
void MergeSort(ElementType A[], int N)
{
ElementType *TmpArray;
TmpArray = malloc(sizeof(ElementType)*N);
if (TmpArray != NULL)
{
MSort(A, TmpArray, 0, N - 1);
free(TmpArray);
}
else
{
FatalError("out of space!!!");
}
}
排序算法--归并排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。