关于归并排序算法（分治法）

来源：百度知道 编辑：UC知道 时间：2024/05/26 21:47:05
谁帮我看看这个算法哪里错了？
#include "stdafx.h"
#include <iostream>
using namespace std;

void MERGE_SORT(int *, int, int);
void MEGRE(int *, int, int);

int _tmain(int argc, _TCHAR* argv[])
{
int arry[8] = {5, 2, 4, 7, 1, 3, 2, 6};
int *temp = arry;
MERGE_SORT(temp, 0, 7);
for(int i = 0; i < 8; ++i)
{
cout << arry[i] << " ";
}
cout << endl;
return 0;
}

void MERGE_SORT(int *arry, int first, int last)
{
if(first < last)
{
int mid = (first + last) / 2;
MERGE_SORT(arry, first, mid);//我觉得这里的调用应该同时进行，如何编呢？
MERGE_SORT(arry, mid + 1, last);
MEGRE(arry, first ,last);
}
}

void MEGRE(int *arry, int first, int last)
{
int mid = (first + last) / 2;
int i3 = mid + 1;
int n1 = i3 - first;
int n2 = last - mid - 1;
int *a = arry;
int *L = new in

你写的太乱了。不完全是他说的漏掉数据问题。而是边界完全有问题，导致了数组内的数据都变成错误的了。看得有点乱。整了个比较规范的给你参考参考。
void merge(int a[] , int temp[] , int Lpos , int Rpos , int RightEnd)
{
int i , LeftEnd , num , tmppos;

LeftEnd = Rpos - 1;
tmppos = Lpos;
num = RightEnd - Lpos + 1;
while (Lpos <= LeftEnd && Rpos <= RightEnd)
if (a[Lpos] <= a[Rpos]) temp[tmppos ++] = a[Lpos ++];
else temp[tmppos ++] = a[Rpos ++];
while (Lpos <= LeftEnd) temp[tmppos ++] = a[Lpos ++];
while (Rpos <= RightEnd) temp[tmppos ++] = a[Rpos ++];
for (i = 0; i < num; i ++)
{
a[RightEnd] = temp[RightEnd];
RightEnd --;
}
}

void msort(int a[] , int temp[] , int L , int r)
{
int c;

if (L < r)
{
c = (L + r) / 2;
msort(a , temp , L , c);
msort(a , temp , c + 1 , r);
merge(a , temp , L , c + 1 , r);
}
}

void mergesort(int a[] , int n) //调用此函数，a为排序数组